So I'll Max Out My Constructive Algorithm Skills

BaoBao the Witch is stuck in a maze with $n$ rows and $n$ columns. The height of the cell in row $i$ and column $j$ is $h_{i,j}$. To get out, BaoBao must find a path that visits each cell exactly once. She can only move to a neighboring cell that shares an edge with her current cell.

BaoBao is very lazy. Every time she climbs up (moves from a cell with a smaller height to a cell with a larger height), her happiness drops. Find a valid path so that the number of climbs is not more than the number of descents.

A valid path is a sequence $(x_1, y_1), (x_2, y_2), \ldots, (x_{n^2}, y_{n^2})$ such that:

• For all $1 \le i \le n^2$, $1 \le x_i, y_i \le n$.
• For all $1 \le i, j \le n^2$ with $i \ne j$, $(x_i, y_i) \ne (x_j, y_j)$.
• For all $2 \le i \le n^2$, $|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$.
• $\sum_{i=2}^{n^2} [h_{x_{i-1},y_{i-1}} < h_{x_i,y_i}] \le \sum_{i=2}^{n^2} [h_{x_{i-1},y_{i-1}} > h_{x_i,y_i}]$, where $[P]$ is 1 when $P$ is true and 0 otherwise.

The heights of all cells form a permutation of $1$ to $n^2$, so you only need to output the height of each cell along a valid path.

There are multiple test cases. The first line contains $T$ ($1 \le T \le 100$), the number of test cases.

Each test case starts with an integer $n$ ($2 \le n \le 64$), the size of the maze. The next $n$ lines each contain $n$ integers $h_{i,1}, h_{i,2}, \ldots, h_{i,n}$ ($1 \le h_{i,j} \le n^2$). All integers in the input form a permutation of $n^2$.

For each test case, print one line with $n^2$ integers separated by spaces. These are the heights of the cells in the order of a valid path. If several answers exist, print any of them. An answer always exists.