Fumo Temple
Contest: EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: interactive

This is an interactive problem.

You are given two positive integers $$$n$$$ and $$$m$$$ ($$$\bf{n \le m}$$$).

The jury has hidden from you a rectangular matrix $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns, where $$$a_{i,j} \in \{ -1, 0, 1 \}$$$ for all $$$1 \le i \le n$$$ and $$$1 \le j \le m$$$. The jury has also selected a cell $$$(i_0, j_0)$$$. Your goal is to find $$$(i_0,j_0)$$$.

In one query, you give a cell $$$(i, j)$$$, then the jury will reply with an integer.

- If $$$(i, j) = (i_0, j_0)$$$, the jury will reply with $$$0$$$.
- Else, let $$$S$$$ be the sum of $$$a_{x,y}$$$ over all $$$x$$$ and $$$y$$$ such that $$$\min(i, i_0) \le x \le \max(i, i_0)$$$ and $$$\min(j, j_0) \le y \le \max(j, j_0)$$$. Then, the jury will reply with $$$|i - i_0| + |j - j_0| + |S|$$$.

Find $$$(i_0, j_0)$$$ by making at most $$$n + 225$$$ queries.

Note: the grader is not adaptive: $$$a$$$ and $$$(i_0,j_0)$$$ are fixed before any queries are made.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m \le 5000$$$) — the numbers of rows and the number of columns of the hidden matrix $$$a$$$ respectively.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$25 \cdot 10^6$$$.

Interaction format:
The interaction for each test case begins by reading the integers $$$n$$$ and $$$m$$$.

To make a query, output "? i j" ($$$1 \le i \le n, 1 \le j \le m$$$) without quotes. Afterwards, you should read one single integer — the answer to your query.

If you receive the integer $$$-1$$$ instead of an answer or a valid value of $$$n$$$ or $$$m$$$, it means your program has made an invalid query, has exceeded the limit of queries, or has given an incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you are ready to give the final answer, output "! i j" ($$$1 \le i \le n, 1 \le j \le m$$$) without quotes — the indices of the hidden cell. After solving a test case, your program should move to the next one immediately. After solving all test cases, your program should be terminated immediately.

After printing a query do not forget to output 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 documentation for other languages.

Hacks

To hack, use the following format:

The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m \le 5000$$$) — the sizes of the hidden matrix.

The second line of each test case contains two integers $$$i_0$$$ and $$$j_0$$$ ($$$1 \le i_0 \le n, 1 \le j_0 \le m$$$) — the hidden cell.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains the string $$$s_i$$$ of length $$$n$$$, consisting only of the characters -, 0, and +. Here, $$$a_{ij} = -1$$$ if $$$s_{ij} = \mathtt{-}$$$, $$$a_{ij} = 0$$$ if $$$s_{ij} = \mathtt{0}$$$, and $$$a_{ij} = 1$$$ if $$$s_{ij} = \mathtt{+}$$$.

The sum of $$$n \cdot m$$$ over all test cases should not exceed $$$25 \cdot 10^6$$$.

As an example, the hack format for the example input is:

$$$\texttt{2}\\ \texttt{3}\,\texttt{4} \\ \texttt{1}\,\texttt{4} \\ \texttt{+0+0} \\ \texttt{+00+} \\ \texttt{0---} \\ \texttt{1}\,\texttt{1}\\\texttt{1}\,\texttt{1}\\\texttt{0}$$$

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
The hidden matrix in the first test case: $$$1$$$$$$0$$$$$$1$$$$$$\color{red}{\textbf{0}}$$$$$$1$$$$$$0$$$$$$0$$$$$$1$$$$$$0$$$$$$-1$$$$$$-1$$$$$$-1$$$

The hidden matrix in the second test case: $$$\color{red}{\textbf{0}}$$$

Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.

Example input:
2
3 4

5

3

5

1 1

0

Example output:
? 1 1

? 3 3

? 3 2

! 1 4

? 1 1

! 1 1

Editorial:
In this solution, we will assume that there is no matrix $$$a$$$ and the interactor just returns some number $$$x$$$ between $$$di + dj \le x \le di + dj + (di + 1)(dj + 1)$$$, where $$$di = |i - i_0|$$$ and $$$dj = |j - j_0|$$$.
Let's first solve for $$$n = 1$$$. Let the hidden cell be $$$(1, j_0)$$$. Let $$$l = 1$$$ and $$$r = m$$$. On each iteration, we will query the cell $$$(1, l)$$$, let the result be $$$x$$$. If $$$x = 0$$$, we are done. Else, we know that $$$j_0 - l \le x \le j_0 - l + (j_0 - l + 1)$$$. Transforming, we get $$$\max(l + 1, \frac{x-1}{2} + l) \le j_0 \le \min(r, x + l)$$$. So, on each iteration, we at least half the length of $$$[l; r]$$$, so we use at most $$$\lceil \log_2(m) \rceil$$$ queries. This allows us to solve the problem in $$$n \cdot \lceil \log_2(m) \rceil$$$ queries, if for each row we assume that the hidden cell is in it and then run the algorithm above.
We will solve the problem recursively, ensuring $$$n \le m$$$. If $$$m \le A$$$ (we will choose $$$A$$$ later), we can solve the problem for the remaining rows in $$$A \cdot \lceil \log_2(A) \rceil$$$ queries.
Else, our objective is to either decrease $$$m$$$ by a lot, or decrease $$$n$$$ by a bit and recurse further. To do that, we will query the three cells $$$(2, \frac{3m}{16}), (2, \frac{m}{2}), (2, \frac{13m}{16})$$$ (choose integer coordinates + things should be pretty symmetrical). This ensures that for large enough $$$m$$$, if we get a large query result $$$> B$$$ ($$$B$$$ is around $$$\frac{3m}{4}$$$), we will know that $$$i_0 \ge 4$$$ must hold, and so we will recurse with $$$n_{new} = n - 3$$$ and $$$m_{new} = m$$$. If not, we will recurse to $$$n_{new} \le m_{new} \le B$$$ ($$$n_{new} \le m_{new}$$$ since we query on the edge of the matrix).
For the model solution below, we take at most $$$63$$$ queries to get to $$$m \le A = 25$$$, so we solve the problem in at most $$$n + 3 \cdot 21 + 25 \cdot \lceil \log_2(25) \rceil = n + 188 \le n + 225$$$ queries. You can get a slightly better constant factor with this solution, or you can even reduce $$$n$$$ by a rate of quicker than $$$1$$$ per $$$1$$$ query.
Complexity: $$$\mathcal{O}(nm)$$$