这是一个交互式问题。

你发现自己身处日本海岸附近的海床上，那里有大量的铁甲贝（Cloyster）标本。因为你刚才试图捕捉其中一只，它们现在对你非常生气。你必须立即找到族群的首领并请求它的原谅。不过，它在哪里呢？

该区域包含 $n^2$ 个方格，排列成 $n$ 行 $n$ 列。每个方格里都藏着一只铁甲贝，每只铁甲贝都有自己的壳。现在，我可以向你透露一些关于铁甲贝鲜为人知的事实：

• 首领拥有最大的壳。显而易见。
• 族群中所有铁甲贝的壳大小各不相同。
• 除了首领之外，每只铁甲贝在与其相邻（包括边相邻和角相邻）的方格中，都有一个壳比它更大的邻居。

你可以查询单个标本的壳的大小。利用这些信息来定位族群的首领。动作要快——如果你不能在 $3n + 210$ 次查询内找到它，铁甲贝就会失去耐心并攻击你！

交互

第一行包含一个整数 $n$ ($2 \le n \le 2000$)，表示区域的大小。你的程序应该首先读取它。之后，你的程序可以进行两种类型的请求：

• “? i j” ($1 \le i, j \le n$) —— 查询第 $i$ 行第 $j$ 列方格中标本的壳的大小。你最多可以使用此查询 $3n + 210$ 次。响应将是一个单独的整数 $a_{ij}$ ($1 \le a_{ij} \le 10^9$)，打印在单独的一行上。
• “! i j” ($1 \le i, j \le n$) —— 回答族群的首领位于第 $i$ 行第 $j$ 列。这应该是你的最后一次查询。你的程序随后应立即终止。

交互器是非自适应的，即壳的大小在程序运行前就已经固定，并且在你的查询过程中不会改变。记得在打印每一行后刷新输出！

样例

输入格式 1

3
1
4
8
9
5

输出格式 1

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

输入格式 2

5
2

输出格式 2

? 4 4
! 1 1

说明

这里是两个样例测试中每只铁甲贝壳的大小：

注意，第二个样例测试中的通信是正确的——即使你的程序不确定答案的正确性，也允许进行猜测。