P4791 [BalticOI 2018] Worm Worries

**This problem is translated from [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day 1 “[Worm Worries](https://boi18-day1-open.kattis.com/problems/boi18.worm)”.** **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$.

**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

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 ```

| Subtask | Score | Constraints | |:------:|:----:|:----:| | $1$ | $10$ | $M = K = 1,\, N = 1\,000\,000,\, Q = 10\,000$ | | $2$ | $22$ | $M = K = 1,\, N = 1\,000\,000,\, Q = 35$ | | $3$ | $12$ | $K = 1,\, N = M = 200,\, Q = 4\,000$ | | $4$ | $19$ | $K = 1,\, N = M = 1\,000,\, Q = 3\,500$ | | $5$ | $14$ | $N = M = K = 100,\, Q = 100\,000$ | | $6$ | $23$ | $N = M = K = 500,\, Q = 150\,000$ | Thanks to Hatsune_Miku for providing the translation. Translated by ChatGPT 5