题目描述

题目译自 BalticOI 2018 Day1「Worm Worries」

本题是一道交互题。

在一个三维空间（我们限制大小为 $N\times M\times K$）内，每个点都有一个正整数参数，记这个参数为 $H[x,\, y,\, z]$（保证 $1\leqslant x \leqslant N\ ,1 \leqslant y \leqslant M\ ,1 \leqslant z \leqslant K$ 且每个参数都不超过 $10^9$）。你最多可以询问 $Q$ 次，找到一个点，使得这个点的参数不小于它周围与它有公共边的所有点的参数，即：

$$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]). $$

特别地，当一个点不在空间直角坐标系的第一卦限内时，它的参数为 $0$。

输入格式

请使用标准输入输出流与交互库进行交互。你可以向交互库询问最多 $Q$ 次，每次可以询问一个点的参数。

输入的第一行包含四个整数 $N,\,M,\,K,\,Q$ （请忽略这一行的其他参数）。在此之后，你可以向交互器提出至多 $Q$ 行形如 ? x y z 的询问，表示「询问坐标为 $(x,\,y,\,z)$ 的点的参数是多少」。对于每一组询问，交互器会输出一行一个整数表示坐标为 $(x,\,y,\,z)$ 的点的参数。

当你找到一组解时，输出一行 ! x y z 表示你找到的答案是 $(x,\,y,\,z)$，并终止程序。此时交互器不会有任何输出。

所有坐标必须满足 $1\leqslant x\leqslant N,\, 1\leqslant y\leqslant M,\, 1\leqslant z\leqslant K$。如果不满足坐标的限制、询问不符合格式或询问超过了 $Q$ 行，交互器会输出 -1 并退出，此时你的程序也应该退出。否则你可能会得到 Runtime Error 或 Time Limit Exceeded 的判定结果。

请注意，你必须在每一次询问之后手动刷新缓存，否则你的程序将会超时，对于各语言，刷新缓存的方法如下：

• Java: 调用 System.out.println() 会自动刷新缓存；
• Python: 调用 print() 会自动刷新缓存；
• C++: cout << endl 可以输出一个换行并刷新缓存。如果使用 printf，请使用 fflush(stdout)；
• Pascal: 调用 Flush(Output)。

为了帮助你更好地完成交互，我们提供了可以复制到你的程序里的可选代码。可选代码使用了较快的输入输出，可能会提高 IO 较慢的 Python 和 Java 语言的程序效率（只与最后两个子任务有关）。

交互器没有使用随机函数，这意味着，每组测试数据都是固定的，与你的程序的询问无关。

样例

样例中，三维空间的大小为 $3\times 1\times 1$，三个位置的参数为 $[10,14,13]$。下面的交互过程中，JUDGE 开头的行冒号后的内容是你需要读入的，而 YOU 开头的行冒号后的内容是你输出的。

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

因为参数 $14$ 大于等于它相邻点的参数（$10$ 和 $13$），所以坐标为 $(2,\,1,\,1)$ 的点满足条件，你一共进行了 $3$ 次查询，小于等于最大允许查询次数 $3$，因此本次交互通过了这组测试数据。

数据范围与提示

子任务	分值	限制
$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$

请注意在 LibreOJ 上共有 $7$ 个子任务，其中第一个子任务为样例。