Description

宝宝女巫被困在一个 $n$ 行 $n$ 列的迷宫中，其中第 $i$ 行第 $j$ 列的单元格高度为 $h_{i,j}$。要走出迷宫，宝宝必须找到一条路径，该路径穿过每个单元格恰好一次。每次她只能移动到与当前单元格共享边的相邻单元格。但是众所周知，宝宝非常懒，所以每当她爬升（即从高度较低的单元格移动到高度较高的单元格）时，她的幸福值会减少。作为她的帮手，你的任务是找到一条有效的路径，使得沿着路径移动时，宝宝爬升的次数不多于她下降的次数。

更正式地说，你需要找到一个序列 $(x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})$，使得：

• 对于所有的 $1 \le i \le n^2$，$1 \le x_i, y_i \le n$；
• 对于所有的 $1 \le i, j \le n^2, i \neq j$，$(x_i, y_i) \neq (x_j, y_j)$；
• 对于所有的 $2 \le i \le n^2$，$|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$；
• $\sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}$，其中 $[P]$ 当 $P$ 为真时等于 $1$，当为假时等于 $0$。

此外，你发现所有单元格的高度都是 $n^2$ 的排列，所以你只需要输出有效路径中每个单元格的高度。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$（$2 \le n \le 64$），表示迷宫的大小。

接下来的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $h_{i, 1}, h_{i, 2}, \cdots, h_{i,n}$（$1 \le h_{i, j} \le n^2$），其中 $h_{i,j}$ 表示第 $i$ 行第 $j$ 列单元格的高度。保证输入中的所有整数构成 $n^2$ 的排列。

Output Format

对于每个测试用例，输出一行，包含 $n^2$ 个由空格分隔的整数，表示有效路径中每个单元格的高度。如果有多个有效答案，你可以输出其中任何一个。很容易证明答案总是存在。

请不要在每行的末尾输出多余的空格，否则你的答案可能会被认为不正确！

翻译来自于：ChatGPT。

1
2
4 3
2 1

4 3 1 2