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

Вид пингвинов, который исследует Blackslex, живет на острове, представляющем собой матрицу с $$$n$$$ строками и $$$n$$$ столбцами. В каждой ячейке матрицы живет ровно один пингвин.

Он обозначил каждого пингвина целым числом от $$$1$$$ до $$$n^2$$$. Через некоторое время некоторые пингвины мигрировали в другую ячейку. После миграции каждый пингвин все еще будет находиться в какой-то ячейке матрицы, и в каждой ячейке будет ровно один пингвин. Ему нужно узнать текущее положение каждого пингвина.

Для этого он может спросить у пингвина, как далеко находится другой пингвин от него.

Формально, для возможной матрицы $$$x$$$, представляющей положение всех пингвинов, обозначим $$$\operatorname{dist}(x, i, j)$$$ как манхэттенское расстояние пингвина $$$i$$$ до пингвина $$$j$$$ в $$$x$$$$$$^{\text{∗}}$$$.

Существует скрытая матрица $$$a$$$ с $$$n$$$ строками и $$$n$$$ столбцами. Вам нужно найти матрицу $$$b$$$, которая удовлетворяет следующим условиям:

• $$$b$$$ имеет $$$n$$$ строк и $$$n$$$ столбцов.
• Каждая ячейка $$$b$$$ содержит целое число от $$$1$$$ до $$$n^2$$$, которое является меткой пингвина. Каждое целое число будет находиться в одной ячейке.
• Для всех $$$1 \leq i, j \leq n^2$$$ выполняется равенство $$$\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$$$.

Для этого вы можете сделать следующий запрос не более чем $$$3n^2 + 150$$$ раз.

• Для выбранных $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n^2$$$), вы получите значение $$$\operatorname{dist}(a, i, j)$$$.

Чтобы задать запрос, выберите два целых числа $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n^2$$$) и выведите '? $$$i$$$ $$$j$$$' (без кавычек) в строку.

Вы получите одно целое число — расстояние между пингвинами $$$i$$$ и $$$j$$$.

Вы можете сделать не более чем $$$3n^2 + 150$$$ запросов в каждом наборе входных данных.

После завершения ваших запросов выведите '!' в строке, затем выведите $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел, $$$j$$$-е целое число в $$$i$$$-й строке равно $$$b_{i,j}$$$.

Ваш вывод должен удовлетворять заданным условиям, и вы можете вывести любое такое $$$b$$$, если возможно несколько. Обратите внимание, что это не считается запросом и не учитывается при подсчете количества сделанных запросов.

После этого переходите к следующему набору входных данных.

Взаимодействие в этой задаче не адаптивно. Другими словами, матрица не меняется в процессе взаимодействия.

Если вы сделаете более $$$3n^2 + 150$$$ запросов для набора входных данных во время взаимодействия, ваша программа должна немедленно завершиться, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит чтение из закрытого потока.

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

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

Взломы

Чтобы сделать взлом, следуйте формату теста ниже.

Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 200$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 100$$$) — размер острова.

Следующие $$$n$$$ строк содержат $$$n$$$ целых чисел, $$$j$$$-е целое число в $$$i$$$-й строке равно $$$a_{i,j}$$$ — метка пингвина в строке $$$i$$$, столбце $$$j$$$.

Должно выполняться условие, что общая сумма всех значений $$$n$$$ по всем наборам входных данных не превышает $$$500$$$.