CF1423M Milutin's Plums

众所周知，李子采摘季节到了！小 Milutin 在一个可以表示为 $n$ 行 $m$ 列的矩阵的果园里种植了李子树。在采摘的过程中，他记录下了所有树的高度，并将其写成了一个 $n$ 行 $m$ 列的矩阵。 晚上有空的时候，他喜欢对自己的果树做各种统计。这一次，他很好奇想要找出自己果园中最矮的树的高度。到目前为止，他已经发现了果园的一些有趣性质。其中有一个性质，他认为对找出最矮的树很有帮助。 形式化地，设 $L(i)$ 表示第 $i$ 行中最矮的树的最左边的位置。他知道对于所有 $1 \le i \le n-1$，都有 $L(i) \le L(i+1)$。此外，如果他取任意若干行和任意若干列组成的子矩阵，对于该子矩阵的所有 $1 \le i \le n'-1$（$n'$ 为子矩阵的行数），仍然有 $L(i) \le L(i+1)$。 由于正值采摘高峰期，他时间紧迫，请你帮他找出果园中最矮的李子树的高度。

本题为交互题。 输入的第一行包含两个整数 $n$ 和 $m$，表示 Milutin 果园的行数和列数。保证 $1 \le n, m \le 10^6$。 接下来的内容为你对交互的查询结果。

一旦你确定了最小值 $r$，你应输出 `! r` 到标准输出。 **交互说明** 你的代码可以查询矩阵中的任意一个元素 $(i, j)$（即第 $i$ 行第 $j$ 列的树的高度）。查询格式为 `? i j`，其中 $1 \le i \le n$，$1 \le j \le m$。 你可以假设矩阵中的每个元素都是 $1$ 到 $10^9$ 之间的整数。 你的解法最多只能使用 $\mathbf{4 \cdot (n + m)}$ 次查询。 本题为交互题。你每输出一行后都需要刷新输出缓冲区。例如，在 C++ 中使用 `fflush(stdout)`，在 Java 中使用 `System.out.flush()`，在 Pascal 中使用 `flush(output)`，在 Python 中使用 `sys.stdout.flush()`。

由 ChatGPT 4.1 翻译