Problem Description

This problem is translated from BalticOI 2018 Day 1 “Worm Worries”.

This is an interactive problem.

In a three-dimensional space (we limit the size to $N \times M \times K$), each point has a positive integer value, denoted by $H[x,\, y,\, z]$ (it is guaranteed that $1 \leqslant x \leqslant N$, $1 \leqslant y \leqslant M$, $1 \leqslant z \leqslant K$, and each value does not exceed $10^9$). You may ask at most $Q$ queries to find a point whose value is greater than or equal to the values of all points that share an edge with it, i.e., $H[x,\,y,\,z]\geqslant\max(H[x+1,\,y,\,z],\, H[x-1,\,y,\,z],\, H[x,\,y+1,\,z],\, H[x,\,y-1,\,z],\, H[x,\,y,\,z+1],\, H[x,\,y,\,z-1]).$

In particular, when a point is not in the first octant of the Cartesian coordinate system, its value is $0$.

Input Format

Please use standard input/output streams to interact with the interactor. You can query the interactor at most $Q$ times, and each time you may ask for the value at one point.

The first line of input contains four integers $N,\, M,\, K,\, Q$ (please ignore the other parameters on this line). After that, you may send to the interactor at most $Q$ lines of queries of the form ? x y z, meaning “ask what the value at coordinate $(x,\,y,\,z)$ is”. For each query, the interactor outputs one line with one integer, which is the value at coordinate $(x,\,y,\,z)$.

When you find a valid answer, output one line ! x y z to indicate that your answer is $(x,\,y,\,z)$, and terminate your program. In this case, the interactor will output nothing.

All coordinates must satisfy $1 \leqslant x \leqslant N$, $1 \leqslant y \leqslant M$, $1 \leqslant z \leqslant K$. If the coordinates do not satisfy the constraints, the query format is invalid, or the number of queries exceeds $Q$, the interactor will output -1 and exit; in this case your program should also exit. Otherwise, you may receive a verdict such as Runtime Error or Time Limit Exceeded.

Note that you must manually flush the output buffer after each query, otherwise your program will time out. For different languages, the flushing methods are as follows:

• Java: calling System.out.println() flushes automatically;
• Python: calling print() flushes automatically;
• C++: cout << endl prints a newline and flushes. If you use printf, use fflush(stdout);
• Pascal: call Flush(Output).

To help you implement the interaction more easily, we provide optional code that you can copy into your program. The optional code uses faster input/output, which may improve the efficiency of Python and Java programs with slower IO (only related to the last two subtasks).

The interactor does not use random functions. This means that each testdata is fixed and does not depend on your queries.

Output Format

To help you implement the interaction, here is an example interaction. In this example, $N=3,\, M=3,\, K=1,\, Q=3$, and the values of the three cells are $\{10,\,14,\,13\}$. Lines starting with JUDGE are the interactor’s output (your program’s standard input), and lines starting with YOU are your program’s output.

JUDGE:      3 1 1 3 123123 fixed 10 14 13
YOU  :      ? 3 1 1
JUDGE:      13
YOU  :      ? 2 1 1
JUDGE:      14
YOU  :      ? 1 1 1
JUDGE:      10
YOU  :      ! 2 1 1

Hint

Thanks to Hatsune_Miku for providing the translation.

Translated by ChatGPT 5