Problem J
Червячьи радости

Вы решили вывести своего домашнего червячка Максимку на выгул и хотели бы найти для него оптимальное место в земле. В поиске идеального места вы решили ограничиться областью пространства в форме параллелограма размерами $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$.

Максимка любит влажные места, и поэтому вы должны поместить его в клетку, влажность которой как минимум не меньше влажности всех соседних клеток (иначе он уползет в соседнюю, более влажную клетку, и его потом будет сложно найти). Другими словами, вам нужно поместить Максимку в клетку-локальный максимум по влажности.

Строго говоря, требуется найти клетку $(x,y,z)$, которая удовлетворяет условию:

Значение влажности вне пределов выбранной области пространства считаем равным $0$ (потому что Максимке очень хочется оставаться в этой области).

Количество клеток, однако, может быть довольно большим, и вам не хотелось бы измерять влажность для всех из них. В этой задаче вы можете взаимодействовать с программой-оценивателем, запрашивая влажность в выбранных клетках по одной. Как только вы нашли подходящее место для Максимки, сообщите его оценивателю и завершите работу.

Интерактивность

На первой строке ввода даны четыре положительные числа: $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)$ является подходящим местом для Максимки, согласно требуемым условиям. После этого оцениватель не будет давать какого-либо ввода.

Все значения $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.

Вы обязаны всегда сбрасывать (flush) буфер стандартного вывода перед зачитыванием следующего ввода, иначе оцениватель может зависнуть в ожидании результата, и ваша программа получит оценку Time Limit Exceeded. Сбрасывание буфера реализуется в различных языках следующим образом:

• Java: System.out.println() автоматически сбрасывает буфер.

• Python: print() автоматически сбрасывает буфер.

• C++: cout << endl; выводит новую строку и сбрасывает буфер. При использовании printf, буфер сбрасывается командой fflush(stdout).

• Pascal: Flush(Output).

Чтобы помочь в реализации взаимодействия с оценивателем, мы предоставляем вспомогательные примеры кода, которые вы можете скопировать к себе в программу. Ссылка на этот код для всех поддерживаемых языков (C++, Pascal, Java, Python) находится на боковой панели страницы задачи в системе Kattis.

Мы особенно рекомендуем использовать этот код, если вы программируете на Java или Python, где процедуры ввода-вывода по умолчанию могут быть недостаточно быстрыми для решения последних двух групп тестов. Вспомогательный код использует оптимизированные алгоритмы ввода-вывода, скорость которых достаточна для реализации корректного решения.

Алгоритм оценивания не является адаптивным. Это значит, что каждому тесту соответствует фиксированный набор значений влажности, который не зависит от того, какие измерения совершает программа.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Пример диалога

В примере ниже область имеет размеры $3\times 1\times 1$, а влажность трех клеток равна 10, 14, 13. Далее приведён пример диалога с оценивающей программой. Строки, начинающиеся со слова JUDGE – это вывод оценивателя Kattis (т.е. ввод для вашей программы). Строки, начинающиеся со слов YOU – это вывод вашей программы.

Т.к. $14$ – это больше чем соседние значения ($10$ и $13$), то клетка $(2,1,1)$ является подходящим местом для Максимки. Использовано было три запроса, что соответствует разрешенному максимуму ($Q=3$). Поэтому данный диалог принимается как корректное решение для данного примера.

 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