Description

Troy wants to play a game with you. The game uses an $R \times C$ grid.

There are $N$ pieces (numbered from $1$ to $N$). The $i$-th piece is placed at $(X_i, Y_i)$. Multiple pieces may be on the same cell.

In one second, Troy can move one piece to a vertically or horizontally adjacent cell. Troy defines the score of a cell as the minimum number of seconds needed to move all $N$ pieces to that cell. Your task is to find the minimum score among all cells on the board.

Troy will not tell you the value of $N$ or the positions of the pieces, but you may ask Troy at most $K$ questions: the score of cell $(p, q)$.

Interactive Strategy

This is an interactive problem.

First, read three integers $R, C, K$, representing the size of the grid and the maximum number of questions you may ask.

After reading this line, your program may ask questions about the score of $(p, q)$ (in the format ? p q), and then you will receive an integer $s$ representing the score of that cell.

Once your program determines the minimum score among all cells on the board, it should output ! Z and terminate, where $Z$ is the final answer.

After outputting each line, you must flush the buffer:

• C/C++: fflush(stdout) or cout << endl
• Java: System.out.flush()
• Pascal: flush(output)

If your output format is incorrect, or you ask more than $K$ questions, your answer will be judged incorrect.

Input Format

None

Output Format

None

1 10 90 3
1 2
1 4
1 10

5 4 170 4
2 3
2 3
4 3
5 1

Hint

Sample Explanation

For sample $1$

The piece positions should be $(1,2)$, $(1,4)$, and $(1,10)$, so the minimum score over the whole board is $8$ (the score of cell $(1,4)$).

For sample $2$

The piece positions should be $(2,3)$, $(2,3)$, $(4,3)$, $(5,1)$.

Constraints

For $100\%$ of the testdata, $1 \le R, C \le 10^7$, $1 \le K \le 170$, $1 \le p \le R$, $1 \le q \le C$, $0 \le s \le 2 \times 10^9$, $1 \le N \le 100$, $1 \le X_i \le R$, $1 \le Y_i \le C$。
For $20\%$ of the testdata, $R = 1$, $C \le 90$, $K = 90$。
For another $20\%$ of the testdata, $R = 1$, $K = 90$。
For another $20\%$ of the testdata, $K = 170$。
For another $20\%$ of the testdata, $K = 100$。
For another $20\%$ of the testdata, $K = 75$。

The spj and interactive library are included in the attached files.

Notes

Translated from Canadian Computing Olympiad 2018 Day 2 A Gradient Descent。

spj author:

Translated by ChatGPT 5