C. Найдите мину
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Вам дано клетчатое поле из $$$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|)$$$.

Ваша задача — определить расположение одной из мин, сделав свои запросы.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^{3}$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^{8}$$$, $$$2 \leq m \leq 10^{8}$$$) — количество строк и столбцов.

Протокол взаимодействия

Для каждого набора входных данных интеракция начинается с чтения $$$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$$$).

Мины должны располагаться в различных позициях.

Пример
Входные данные
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

Примечание

В первом наборе входных данных мы сначала спрашиваем про верхний левый угол $$$(1, 1)$$$ и получаем результат $$$3$$$, что означает, что есть мина на побочной диагонали, и нет мин над ней.

На картинке ниже каждая клетка содержит число, обозначающее расстояние до синей клетки. Зеленые клетки — кандидаты, в которых содержится ближайшая мина.

Затем мы спрашиваем три клетки на диагонали и в последнем запросе мы получаем результат $$$0$$$, что означает, что одна из мин найдена на позиции $$$(2, 3)$$$.

Вторая мина располагалась на позиции $$$(3, 2)$$$.

Во втором наборе входных данных мы сначала спрашиваем нижний правый угол $$$(5, 5)$$$ и получаем результат $$$1$$$, который означает, что одна из двух соседних клеток содержит мину, назовем ее миной $$$1$$$.

Затем мы спрашиваем клетку $$$(2, 2)$$$. Можем заметить, что зеленые клетки не пересекаются с зелеными клетками из первого запроса, поэтому они содержат оставшуюся мину, назовем ее миной $$$2$$$.

Запрос $$$3$$$ — это клетка $$$(3, 3)$$$. Эти клетки содержат мину $$$1$$$, но мы все еще не знаем, где именно. Тем не менее, мы можем определить, что единственной возможной клеткой для мины $$$2$$$ является клетка $$$(1, 1)$$$, потому что все остальные кандидаты находятся на дистанции менее $$$3$$$ для этого запроса.