IOI 2025 - Migrations

This is an interactive problem.

The species of penguins that Blackslex is researching lives on an island that is a grid with $$$n$$$ rows and $$$n$$$ columns. Exactly one penguin lives in each one cell of the grid.

He labelled each penguin as an integer from $$$1$$$ to $$$n^2$$$. After some time, some penguins migrated to another cell. After migration, every penguin will still be in some cell on the grid, and every cell contains exactly one penguin. He needs the current position of every penguin.

To do so, he can ask a penguin how far another penguin is from it.

Formally, for a possible grid $$$x$$$ representing the position of all penguins, denote $$$\operatorname{dist}(x, i, j)$$$ as the Manhattan distance of the penguin $$$i$$$ to the penguin $$$j$$$ in $$$x$$$$$$^{\text{∗}}$$$.

There is a hidden grid $$$a$$$ with $$$n$$$ rows and $$$n$$$ columns. You need to find a grid $$$b$$$ that satisfies

$$$b$$$ has $$$n$$$ rows and $$$n$$$ columns.
Each cell of $$$b$$$ contains an integer from $$$1$$$ to $$$n^2$$$, which is a penguin's label. Each integer will be in a single cell.
For all $$$1 \leq i, j \leq n^2$$$, it holds that $$$\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$$$.

To do so, you may make the following query no more than $$$3n^2 + 150$$$ times.

Given $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n^2$$$), receive the value of $$$\operatorname{dist}(a, i, j)$$$.

$$$^{\text{∗}}$$$Let $$$r_i$$$, $$$c_i$$$ denote the row and column that the penguin $$$i$$$ is in, and denote the same for $$$r_j$$$, $$$c_j$$$, then the Manhattan distance is $$$|r_i - r_j| + |c_i - c_j|$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 200$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the size of the island.

It is guaranteed that the total sum of all values of $$$n$$$ across all test cases does not exceed $$$500$$$.

Interaction

To ask a query, pick two integer $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n^2$$$) and print "? $$$i$$$ $$$j$$$" (without quotes) to a line.

You will receive a single integer, which is the distance between penguins $$$i$$$ and $$$j$$$.

You may make no more than $$$3n^2 + 150$$$ queries in each test case.

After you finish your queries, output "!" in a line, then output $$$n$$$ lines, each containing $$$n$$$ integers, the $$$j$$$-th integer on the $$$i$$$-th line is $$$b_{i,j}$$$.

Your output must satisfy the conditions given, and you may output any such $$$b$$$ if multiple are possible. Note that this is not considered a query and is not taken into account when counting the number of queries asked.

After this, proceed to the next test case.

The interactor in this task is not adaptive. In other words, the grid does not change during the interaction.

If you make more than $$$3n^2 + 150$$$ queries in a test case during an interaction, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see the documentation for other languages.

Hacks

To hack, follow the test format below.

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the size of the island.

The next $$$n$$$ lines contain $$$n$$$ integers, the $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{i,j}$$$ — the label of the penguin on row $$$i$$$, column $$$j$$$.

It must hold that the total sum of all values of $$$n$$$ across all test cases does not exceed $$$500$$$.

Note

Note that additional lines are for ease of reading. Your solution should not output these additional lines.

In the first test case, the grid $$$a$$$ is

1	4
2	3

In the second test case, the grid $$$a$$$ is

9	1	3
4	2	7
8	5	6

The interaction is as follows.

Contestant	Judge	Description
	2	Start of the first test case. The island has size $$$n=2$$$.
? 1 2		The contestant asks for the distance of penguin labelled $$$1$$$ and $$$2$$$.
	1	The distance of penguin labelled $$$1$$$ and $$$2$$$ is $$$1$$$.
? 1 3		The contestant asks for the distance of penguin labelled $$$1$$$ and $$$3$$$.
	2	The distance of penguin labelled $$$1$$$ and $$$3$$$ is $$$2$$$.
? 1 4		The contestant asks for the distance of penguin labelled $$$1$$$ and $$$4$$$.
	1	The distance of penguin labelled $$$1$$$ and $$$4$$$ is $$$1$$$.
? 2 3		The contestant asks for the distance of penguin labelled $$$2$$$ and $$$3$$$.
	1	The distance of penguin labelled $$$2$$$ and $$$3$$$ is $$$1$$$.
? 2 4		The contestant asks for the distance of penguin labelled $$$2$$$ and $$$4$$$.
	2	The distance of penguin labelled $$$2$$$ and $$$4$$$ is $$$2$$$.
? 3 4		The contestant asks for the distance of penguin labelled $$$3$$$ and $$$4$$$.
	1	The distance of penguin labelled $$$3$$$ and $$$4$$$ is $$$1$$$.
!		The contestant determined a possible grid $$$b$$$.
3 4		Note that the grid need not be exactly the same, but it must hold that $$$\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$$$ for all $$$1 \leq i, j \leq n^2$$$.
2 1
	3	Start of the second test case. The island has size $$$n=3$$$.
? 1 8		The contestant asks for the distance of penguin labelled $$$1$$$ and $$$8$$$.
	3	The distance of penguin labelled $$$1$$$ and $$$8$$$ is $$$3$$$.
!		The contestant determined a possible grid $$$b$$$.
9 1 3
4 2 7
8 5 6

Blackslex and Penguin Migration

Examples