你正在寻找一个土壤中的位置来放置你的宠物蠕虫 Maximus。你将搜索范围限制在一个尺寸为 $N \times M \times K$ 厘米的盒状区域内，该区域被划分为一个三维立方厘米网格，网格中的位置标记为 $(x, y, z)$（其中 $1 \le x \le N, 1 \le y \le M, 1 \le z \le K$）。每个单元格都有一定的湿度 $H[x, y, z]$，这是一个范围在 $1 \dots 10^9$ 之间的整数。你可以使用特殊的传感器测量任何单元格的湿度。
Maximus 喜欢潮湿的地方，因此你需要将它放在一个湿度至少不低于其相邻单元格的单元格中，否则它会离开，你将很难找到它。换句话说，你需要将 Maximus 放置在一个局部极大值点。更准确地说，你需要找到一个单元格 $(x, y, z)$，使得：
$$H[x, y, z] \ge \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$（因为 Maximus 必须待在盒子内）。
然而，单元格的数量可能非常大，因此你不能测量所有单元格的湿度。因此，在本题中，你可以与交互器进行交互，询问给定点的湿度。当你找到适合 Maximus 的位置时，将该位置告知交互器。
交互
输入的第一行包含四个正整数：$N, M, K$ 和 $Q$，其中 $N, M, K$ 是盒子的尺寸，$Q$ 是你最多可以进行的测量次数。
之后，你可以向标准输出写入最多 $Q$ 行格式为 “? x y z” 的内容。这表示询问点 $(x, y, z)$ 的湿度值。对于每一行这样的询问，交互器将返回一行包含整数 $H[x, y, z]$ 的内容，你的程序可以从标准输入中读取该值。
在所有这些询问之后，你的程序必须写入恰好一行格式为 “! x y z” 的内容并终止。这表示点 $(x, y, z)$ 是根据上述标准适合 Maximus 的位置。交互器不会对该输出做出响应。
所有的 $x, y, z$ 值必须满足 $1 \le x \le N, 1 \le y \le M, 1 \le z \le K$。如果不满足，或者某一行格式无效，或者你询问的次数超过了 $Q$，交互器将返回 -1 并退出。如果发生这种情况，你的程序也应退出。如果程序继续运行，可能会错误地获得运行时错误（Runtime Error）或超出时间限制（Time Limit Exceeded）的判决。
你必须确保在读取交互器的响应之前刷新标准输出，否则你的程序可能会被判为超出时间限制。在支持的语言中，操作如下：
- Java:
System.out.println()会自动刷新。 - Python:
print()会自动刷新。 - C++:
cout << endl;在写入换行符的同时会刷新。如果使用printf，请使用fflush(stdout)。 - Pascal:
Flush(Output)。
为了帮助处理交互，我们提供了可选的辅助代码，你可以将其复制到你的程序中。所有支持语言（C++、Pascal、Java、Python）的辅助代码链接可以在 Kattis 题目页面的侧边栏中找到。辅助代码还使用了快速输入/输出例程，这对于 Python 和 Java 可能很有用（仅对最后两组测试数据相关）。
交互器是非自适应的；也就是说，每个测试用例都有一组固定的湿度值，这些值不依赖于程序执行的测量。
子任务
你的解决方案将在多组测试数据上进行测试，每组测试数据都有一定的分值。每组测试数据包含多个测试用例。要获得某组测试数据的分数，你需要解决该组中的所有测试用例。你的最终得分为单次提交所获得的最高分数。
| 组别 | 分值 | 数据范围 |
|---|---|---|
| 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$ |
样例
Kattis 上有一个样例测试用例。在这个样例中，盒子的尺寸为 $3 \times 1 \times 1$，三个单元格的湿度为 $\{10, 14, 13\}$。下面是一个交互示例，其中以 JUDGE 开头的行是 Kattis 的输出（即你程序的输入），以 YOU 开头的行是你程序的输出。
由于 14 确实大于或等于相邻值（10 和 13），因此位置 $(2, 1, 1)$ 是 Maximus 的合适位置，并且你使用了三次查询，这达到了允许的最大次数（$Q = 3$）。因此，此交互在样例上会得到 Accepted。
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
输入格式 1
3 1 1 3 123123 fixed 10 14 13
输出格式 1
! 2 1 1