Это интерактивная задача.
Вам дано клетчатое поле из \(n\) строк и \(m\) столбцов. Координаты \((x, y)\) обозначают клетку на поле, где \(x\) (\(1 \leq x \leq n\)) — номер строки, начиная сверху, и \(y\) (\(1 \leq y \leq m\)) — номер столбца, начиная слева. Гарантируется, что на поле ровно \(2\) мины в различных клетках, обозначенных \((x_1, y_1)\) и \((x_2, y_2)\). Вы можете сделать не более \(4\) запросов к интерактору, и после этих запросов вы должны предоставить расположение одной из мин.
В каждом запросе вы выбираете позицию на поле \((x, y)\), и в качестве ответа вы получите манхэтонское расстояние от выбранной позиции до ближайшей из двух мин, то есть значение \(\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)\).
Ваша задача — определить расположение одной из мин, сделав свои запросы.
Протокол взаимодействия
Для каждого набора входных данных интеракция начинается с чтения \(n\) и \(m\).
Затем вы можете сделать не более \(4\) запросов следующим образом:
«? x y» (\(1 \leq x \leq n\) и \(1 \leq y \leq m\))
После каждого из них вы должны прочитать число \(d\), которое равняется \(\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)\).
Когда вы нашли расположение любой из мин, выведите в единственной строке «! x y» (без кавычек), обозначающие строку и столбец для этой мины. Вывод ответа не считается за запрос.
После вывода ответа ваша программа должна продолжить решать оставшиеся тестовые случаи или завершиться, если все тестовые случаи были решены.
Интерактор в этой задаче не является адаптивным: расположение мин зафиксировано заранее и не зависит от запросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы:
Чтобы сделать взлом, используйте следующий формат:
В первой строке находится одно целое число \(t\) (\(1 \leq t \leq 3 \cdot 10^{3}\)) — количество наборов входных данных.
Описание каждого тестового случая должно состоять из трех строк.
Первая строка содержит два целых числа \(n\) и \(m\) (\(2 \leq n \leq 10^{8}\), \(2 \leq m \leq 10^{8}\)) — количество строк и столбцов.
Вторая строка содержит координаты первой мины \(x_1\) и \(y_1\)(\(1 \leq x_1 \leq n\), \(1 \leq y_1 \leq m\)).
Третья строка содержит координаты второй мины \(x_2\) и \(y_2\)(\(1 \leq x_2 \leq n\), \(1 \leq y_2 \leq m\)).
Мины должны располагаться в различных позициях.
Примечание
В первом наборе входных данных мы сначала спрашиваем про верхний левый угол \((1, 1)\) и получаем результат \(3\), что означает, что есть мина на побочной диагонали, и нет мин над ней.
На картинке ниже каждая клетка содержит число, обозначающее расстояние до синей клетки. Зеленые клетки — кандидаты, в которых содержится ближайшая мина.
Затем мы спрашиваем три клетки на диагонали и в последнем запросе мы получаем результат \(0\), что означает, что одна из мин найдена на позиции \((2, 3)\).
Вторая мина располагалась на позиции \((3, 2)\).
Во втором наборе входных данных мы сначала спрашиваем нижний правый угол \((5, 5)\) и получаем результат \(1\), который означает, что одна из двух соседних клеток содержит мину, назовем ее миной \(1\).
Затем мы спрашиваем клетку \((2, 2)\). Можем заметить, что зеленые клетки не пересекаются с зелеными клетками из первого запроса, поэтому они содержат оставшуюся мину, назовем ее миной \(2\).
Запрос \(3\) — это клетка \((3, 3)\). Эти клетки содержат мину \(1\), но мы все еще не знаем, где именно. Тем не менее, мы можем определить, что единственной возможной клеткой для мины \(2\) является клетка \((1, 1)\), потому что все остальные кандидаты находятся на дистанции менее \(3\) для этого запроса.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 4
3
2
2
0
5 5
1
2
3
|
? 1 1
? 1 4
? 4 1
? 2 3
! 2 3
? 5 5
? 2 2
? 3 3
! 1 1
|