Задача . H. Храм фумо

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

Даны два натуральных числа \(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}\)