在塞尔柯克的 Linglie Hill 升起旗帜。CC BY-SA 2.0，由 Jim Barton 上传至维基共享资源

Belle Aire People’s Country 的国王提出了一个新计划：他听说了一个名为“山丘之王”（King of the Hill）的流行现象，他也想成为其中一员。为此，他命令你在他大小为 $n \times n$ 的正方形王国中，将一面旗帜插在最高的山丘上。你获得了一套非常昂贵的（镶嵌着黄金和珠宝）基于卫星的高度测量系统。这套设备非常精确：王国中每个位置的高度都由互不相同的整数表示。然而，为了削减成本，在向国王汇报之前，你最多只被允许进行 $10n + 100$ 次测量。

此外，你确切地知道，有且仅有一个点是绝对的最高点：这是唯一一个其高度大于其在王国内（最多四个）正交相邻点高度的点。换句话说，除了全局最大值之外，不存在其他局部极大值。

交互

这是一个交互式问题。你的程序将与一个交互器（interactor）进行交互，交互器会读取你程序的标准输出，并写入你程序的标准输入。交互需要遵循以下特定的协议：

交互器首先会发送一行，包含一个整数 $n$ ($1 \le n \le 10\,000$)，表示王国的宽度和高度。

然后，你的程序最多可以进行 $10n + 100$ 次询问，以找到王国中的最高点。每次询问通过打印一行格式为 ? x y ($1 \le x, y \le n$) 的内容来进行。交互器将回应一个整数 $v$ ($1 \le v \le 10^9$)，表示坐标 $(x, y)$ 处的高度。

当你确定了王国中最高点的高度 $v$ 时，打印一行格式为 ! v 的内容，之后交互将停止。打印答案不计入询问次数。

交互器是非自适应的：王国中的高度在最开始就是固定好的，不依赖于你的询问。

请确保在每次写入后刷新缓冲区（flush the buffer）。

我们提供了一个测试工具以帮助你开发解决方案。

使用超过 $10n + 100$ 次询问将导致答案错误（Wrong Answer）。

样例

输入样例 1

3
3
9
4
8
7

输出样例 1

? 2 1
? 2 2
? 2 3
? 3 2
? 1 2
! 9

输入样例 2

4
600000000
864213579
864297531
987654321
123456789
975318642

输出样例 2

? 3 3
? 2 3
? 2 2
? 1 2
? 1 1
? 1 3
! 987654321