CF1797C.Li Hua and Chess

This is an interactive problem.

Li Ming and Li Hua are playing a game. Li Hua has a chessboard of size $n\times m$. Denote $(r, c)$ ($1\le r\le n, 1\le c\le m$) as the cell on the $r$-th row from the top and on the $c$-th column from the left. Li Ming put a king on the chessboard and Li Hua needs to guess its position.

Li Hua can ask Li Ming no more than $3$ questions. In each question, he can choose a cell and ask the minimum steps needed to move the king to the chosen cell. Each question is independent, which means the king doesn't actually move.

A king can move from $(x,y)$ to $(x',y')$ if and only if $\max{|x-x'|,|y-y'|}=1$ (shown in the following picture).

The position of the king is chosen before the interaction.

Suppose you were Li Hua, please solve this problem.

Interaction

The first line contains the number of test cases $t$ ($1 \le t \le 10^3$).

The first line of each test case contains two integers $n,m$ ($1\le n,m\le 10^9$) — the size of the chessboard, and then the interaction begins.

To ask a question, print "? $r$ $c$" (without quotes, $1 \leq r \leq n, 1 \leq c \leq m$). Then you should input the response from standard input — the minimum steps the king needs to move to the chosen cell.

If your program has asked an invalid question or has run out of questions, the interactor will terminate immediately and your program will get a verdict Wrong answer.

To give the final answer, print "! $r$ $c$" (without the quotes, $(r,c)$ is the king's initial coordinate). Note that giving this answer is not counted towards the limit of $3$ questions.

After asking a question do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

To hack, use the following format.

The first line should contain a single integer $t$ ($1 \le t \le 10^3$).

The first and only line of each test case should contain four integers $n,m,r,c$ ($1\le r\le n\le 10^9,1\le c\le m\le 10^9$).

这是一个交互式问题。

李明和李华正在玩一个游戏。李华有一个大小为 $n\times m$ 的棋盘。记 $(r, c)$（其中 $1\le r\le n$，$1\le c\le m$）为从上往下第 $r$ 行、从左往右第 $c$ 列的格子。李明在棋盘上放置了一个国王（King），李华需要猜出它的位置。

李华最多可以向李明提出 $3$ 个问题。在每个问题中，他可以选择一个格子，并询问国王移动到该格子所需的最少步数。每次提问相互独立，即国王实际上并不移动。

国王可以从 $(x,y)$ 移动到 $(x',y')$ 当且仅当 $\max{|x-x'|,|y-y'|}=1$（如下图所示）。

国王的初始位置在交互开始前就已经选定。

假设你是李华，请解决这个问题。

交互方式

第一行包含测试用例数量 $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$）。然后你需要从标准输入读入响应——即国王移动到所选格子所需的最少步数。

如果你的程序提出了非法问题，或已用完全部 $3$ 次提问机会，交互器将立即终止，你的程序将被判为“答案错误”。

要给出最终答案，请输出 "! $r$ $c$"（不带引号，$(r,c)$ 即为国王的初始坐标）。注意：输出最终答案不计入 $3$ 次提问次数限制。

每次提问后，不要忘记输出换行符并刷新输出缓冲区；否则你会收到“空闲时间超限”（Idleness limit exceeded）判据。为此，请使用以下方式：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参考相应文档。

Hack（构造数据）

用于 Hack 时，请使用如下格式：

第一行应包含一个整数 $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$）。

In test case 1, the king is at $(2,2)$. It takes $1$ step to move to $(2,3)$ and $2$ steps to move to $(2,4)$.

Note that the questions may not seem sensible. They are just a sample of questions you may ask.

在测试用例 1 中，国王位于 $(2,2)$。它需要 $1$ 步移动到 $(2,3)$，需要 $2$ 步移动到 $(2,4)$。

注意：这些问题可能看起来不太合理。它们仅是你可能提出的问题的一个示例。