A16806. Blackslex and Penguin Migration

[IOI 2025 - Migrations](https://oj.uz/problem/view/IOI25_migrations)

本题为交互题。

Blackslex 正在研究的一种企鹅居住在一个 $n$ 行 $n$ 列的岛屿网格上。每个格子里恰好有一只企鹅。

他把每只企鹅编号为 $1$ 到 $n^2$。经过一段时间后，有些企鹅迁移到了其他格子。迁移之后，仍然每只企鹅会在某个格子里，并且每个格子都有且仅有一只企鹅。他现在需要获得每只企鹅的当前位置。

为此，他可以向一只企鹅询问与另一只企鹅的距离。

具体来说，设 $x$ 为某种企鹅在网格中的位置方案，$\operatorname{dist}(x, i, j)$ 表示企鹅 $i$ 与企鹅 $j$ 在 $x$ 网格中的曼哈顿距离 $^{\ast}$。

现在有一个隐藏的网格 $a$，包含 $n$ 行 $n$ 列。你需要找出一个网格 $b$，满足以下条件：

- $b$ 是 $n$ 行 $n$ 列的网格。
- 每个格子填入 $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)$ 的值。

$^{\ast}$ 设 $r_i$，$c_i$ 分别为企鹅 $i$ 所在的行列位置，同理 $r_j$，$c_j$ 表示企鹅 $j$ 的行列，则曼哈顿距离为 $|r_i-r_j|+|c_i-c_j|$。

每个测试点包含多组测试数据。第一行包含整数 $t$（$1 \leq t \leq 200$）——测试数据的组数。

每组数据的第一行包含一个整数 $n$（$2 \leq n \leq 100$）——岛屿的边长。

保证所有测试数据的 $n$ 之和不超过 $500$。

（本题为交互题，无固定输出格式。参见原题交互协议实现。）

注意附加的换行仅供易读，实际输出中不应输出这些内容。

在第一个测试用例中，隐藏网格 $a$ 是

1423

在第二个测试用例中，隐藏网格 $a$ 是

913427856

交互过程示例如下：

Contestant Judge Description

2 // 第一组数据开始，岛屿大小为 $n=2$
? 1 2 // 选手查询企鹅1和2的距离
1 // 企鹅1和2的距离为1
? 1 3
2
? 1 4
1
? 2 3
1
? 2 4
2
? 3 4
1
! // 选手确定了一个可能的网格 $b$
3 4

注意，所提交的网格不需要与隐藏网格完全一致，但需满足对所有 $1 \leq i, j \leq n^2$，都有 $\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$。

2 // 第二组数据开始，岛屿大小为 $n=3$
? 1 8 // 选手查询企鹅1和8的距离
3
!
9 1 3
4 2 7
8 5 6