这是一个交互问题。
李明和李华正在玩游戏。李华有一个大小为 $$$n\times m$$$ 的棋盘。将 $$$(r, c)$$$ ($$$1\le r\le n, 1\le c\le m$$$) 表示为从顶部开始的第 $$$r$$$ 行和从左边开始的第 $$$c$$$ 列上的单元格。李明在棋盘上放了一个王,李华需要猜测它的位置。
李华最多可以问李明 $$$3$$$ 问题。在每个问题中,他可以选择一个单元格并询问将国王移动到所选单元格所需的最少步骤。每个问题都是独立的,这意味着国王实际上并没有移动。
当且仅当 $$$\max\{|x-x'|,|y-y'|\}=1$$$(如下图所示)时,国王可以从 $$$(x,y)$$$ 移动到 $$$(x',y')$$$。
国王的位置是在互动之前选择的。
假设你是李华,请解决这个问题。
互动
第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。
每个测试用例的第一行包含两个整数 $$$n,m$$$ ($$$1\le n,m\le 10^9$$$) – 棋盘的大小,然后交互开始。
要提出问题,请打印“? $$$r$$$ $$$c$$$”(不带引号,$$$1 \leq r \leq n, 1 \leq c \leq m$$$)。然后,您应该输入标准输入的响应 - 国王移动到所选单元格所需的最少步数。
如果您的程序提出了无效问题或问题已用完,交互器将立即终止,您的程序将得到错误答案。
要给出最终答案,请打印“! $$$r$$$ $$$c$$$”(不带引号,$$$(r,c)$$$ 是国王的初始坐标)。请注意,给出此答案不计入 $$$3$$$ 问题的限制。
提出问题后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式。
第一行应包含单个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$)。
每个测试用例的第一行也是唯一一行应包含四个整数 $$$n,m,r,c$$$ ($$$1\le r\le n\le 10^9,1\le c\le m\le 10^9$$$)。
示例
输入 #1
2 3 4 1 2 5 3 3 1 2
输出 #1
? 2 3 ? 2 4 ! 2 2 ? 2 2 ? 5 2 ? 5 3 ! 5 1
注意
在测试用例 1 中,国王位于 $$$(2,2)$$$。需要 $$$1$$$ 步才能移动到 $$$(2,3)$$$,需要 $$$2$$$ 步才能移动到 $$$(2,4)$$$。
请注意,这些问题可能看起来不合理。它们只是您可能会问的问题的示例。