Troy 想要和你玩一个游戏。

他有一个 $R$ 行 $C$ 列的网格。行从 $1$ 到 $R$ 编号，列从 $1$ 到 $C$ 编号。令第 $p$ 行第 $q$ 列的单元格表示为 $(p, q)$。

网格中有 $N$ 个编号为 $1$ 到 $N$ 的标记。标记 $i$ 位于 $(X_i, Y_i)$，其中 $1 \le X_i \le R$ 且 $1 \le Y_i \le C$。同一个单元格内可能有多个标记。在每一秒内，Troy 可以将一个标记移动到水平或垂直相邻的单元格。单元格的得分定义为 Troy 将所有标记移动到该单元格所需的最少秒数之和。

你的目标是找到网格中任意单元格的最小得分。遗憾的是，Troy 不会告诉你标记的数量或它们的位置。但是，你可以向他提问。你可以询问 Troy 任意单元格 $(p, q)$ 的得分。在 Troy 感到厌烦之前，你最多可以询问 $K$ 次。

交互

这是一个交互式问题：输入将根据你的程序生成的询问给出。

首先，读取一行包含三个整数 $R, C, K$ ($1 \le R, C \le 10\,000\,000$; $1 \le K \le 170$)。

在你的程序读取该行后，可以开始提问。

若要询问关于 $(p, q)$ ($1 \le p \le R; 1 \le q \le C$) 的得分，请按格式 ? p q 输出一行。然后，读取包含一个整数 $s$ ($0 \le s \le 2\,000\,000\,000$) 的一行，即 $(p, q)$ 的得分。

一旦你的程序确定了最小得分为 $Z$，请按格式 ! Z 输出一行。你的程序必须在输出此行后立即终止。

每次输出后必须刷新缓冲区，包括最后一行。刷新缓冲区的方法：在 C/C++ 中使用 fflush(stdout) 或 cout << endl；在 Java 中使用 System.out.flush()；在 Pascal 中使用 flush(output)。

如果输出格式错误或询问次数超过 $K$ 次，你将获得错误判决（incorrect verdict）。

对于每个测试用例，评测系统将拥有固定的整数值 $N, R, C, K, X_1, \dots, X_N, Y_1, \dots, Y_N$ ($1 \le N \le 100; 1 \le X_i \le R; 1 \le Y_i \le C$)。这些值在程序运行期间保持不变。也就是说，评测系统不是自适应的。

子任务

• 对于 25 分中的 5 分，$R = 1, C \le 90$ 且 $K = 90$。
• 对于另外 5 分，$R = 1$ 且 $K = 90$。
• 对于另外 5 分，$K = 170$。
• 对于另外 5 分，$K = 100$。
• 对于剩余 5 分，$K = 75$。

样例

样例输入 1

1 10 90
9
11
8

样例输出 1

? 1 3
? 1 7
? 1 4
! 8

说明 1

该样例对应位于 $(1, 2), (1, 4)$ 和 $(1, 10)$ 的标记。保证此样例与评测系统中的样例测试匹配。

单元格 $(1, 3)$ 的得分为 $1 + 1 + 7 = 9$。 单元格 $(1, 7)$ 的得分为 $5 + 3 + 3 = 11$。 单元格 $(1, 4)$ 的得分为 $2 + 0 + 6 = 8$，这是网格中的最小值。

此示例中各列的得分信息如下：

样例输入 2

5 4 170
11
15
7

样例输出 2

? 2 4
? 1 4
? 3 3
! 7

说明 2

该样例对应位于 $(2, 3), (2, 3), (4, 3)$ 和 $(5, 1)$ 的标记。