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

Даны два натуральных числа $$$n$$$ и $$$m$$$ ($$$\bf{n \le m}$$$).

Жюри спрятало от вас прямоугольную матрицу $$$a$$$ с $$$n$$$ рядами и $$$m$$$ столбцами, где $$$a_{i,j} \in \{ -1, 0, 1 \}$$$ для всех $$$1 \le i \le n$$$ и $$$1 \le j \le m$$$. Жюри также выбрало клетку $$$(i_0, j_0)$$$. Ваша задача — найти $$$(i_0,j_0)$$$.

В одином запросе вы выбираете клетку $$$(i, j)$$$, после чего жюри сообщает вам одно целое число.

• Если $$$(i, j) = (i_0, j_0)$$$, то жюри сообщает число $$$0$$$.
• Иначе пусть $$$S$$$ — это сумма $$$a_{x,y}$$$ по всем $$$x$$$ и $$$y$$$ таким, что $$$\min(i, i_0) \le x \le \max(i, i_0)$$$ и $$$\min(j, j_0) \le y \le \max(j, j_0)$$$. Тогда жюри сообщает число $$$|i - i_0| + |j - j_0| + |S|$$$.

Найдите $$$(i_0, j_0)$$$, сделав не более чем $$$n + 225$$$ запросов.

Примечание: проверяющая программа не является адаптивной: $$$a$$$ и $$$(i_0,j_0)$$$ фиксируются до выполнения каких-либо запросов.

Взаимодействие для каждого набора входных данных начинается с чтения целых чисел $$$n$$$ и $$$m$$$.

Для формирования запроса выведите "? i j" ($$$1 \le i \le n, 1 \le j \le m$$$) без кавычек. После этого вы должны прочитать одно целое число — ответ на ваш запрос.

Если вместо ответа или допустимого значения $$$n$$$ или $$$m$$$ вы получите целое число $$$-1$$$, то это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неверный ответ на предыдущем наборе входных данных. При получении вердикта «Неправильный ответ» ваша программа должна немедленно завершиться. В противном случае можно получить произвольный вердикт, поскольку решение будет продолжать считывать данные из закрытого потока.

Когда вы будете готовы дать окончательный ответ, выведите "! i j" ($$$1 \le i \le n, 1 \le j \le m$$$) без кавычек — индексы загаданной клетки. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы

Для взлома используйте следующий формат.

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le m \le 5000$$$) — количество строк и количество столбцов в матрице соответственно.

Вторая строка каждого набора входных данных содержит два целых числа $$$i_0$$$ и $$$j_0$$$ ($$$1 \le i_0 \le n, 1 \le j_0 \le m$$$) — индексы спрятанной клетки.

После следует $$$n$$$ строк. В $$$i$$$-й из них содержится строка $$$s_i$$$ длины $$$n$$$, состоящая только из символов -, 0, и +. Здесь $$$a_{ij} = -1$$$ если $$$s_{ij} = \mathtt{-}$$$, $$$a_{ij} = 0$$$ если $$$s_{ij} = \mathtt{0}$$$ и $$$a_{ij} = 1$$$ если $$$s_{ij} = \mathtt{+}$$$.

Сумма $$$n \cdot m$$$ по всем наборам входных данных не должна превышать $$$25 \cdot 10^6$$$.

Например, формат взлома для теста из условия:

$$$\texttt{2}\\ \texttt{3}\,\texttt{4} \\ \texttt{1}\,\texttt{4} \\ \texttt{+0+0} \\ \texttt{+00+} \\ \texttt{0---} \\ \texttt{1}\,\texttt{1}\\\texttt{1}\,\texttt{1}\\\texttt{0}$$$