CF1713E.Cross Swapping

You are given a square matrix $A$ of size $n \times n$ whose elements are integers. We will denote the element on the intersection of the $i$-th row and the $j$-th column as $A_{i,j}$.

You can perform operations on the matrix. In each operation, you can choose an integer $k$, then for each index $i$ ($1 \leq i \leq n$), swap $A_{i, k}$ with $A_{k, i}$. Note that cell $A_{k, k}$ remains unchanged.

For example, for $n = 4$ and $k = 3$, this matrix will be transformed like this:

The operation $k = 3$ swaps the blue row with the green column.

You can perform this operation any number of times. Find the lexicographically smallest matrix$^\dagger$ you can obtain after performing arbitrary number of operations.

${}^\dagger$ For two matrices $A$ and $B$ of size $n \times n$, let $a_{(i-1) \cdot n + j} = A_{i,j}$ and $b_{(i-1) \cdot n + j} = B_{i,j}$. Then, the matrix $A$ is lexicographically smaller than the matrix $B$ when there exists an index $i$ ($1 \leq i \leq n^2$) such that $a_i \lt b_i$ and for all indices $j$ such that $1 \leq j \lt i$, $a_j = b_j$.

给你一个 $n \times n$ 的方阵 $A$，其元素均为整数。我们用 $A_{i,j}$ 表示第 $i$ 行与第 $j$ 列交叉处的元素。

你可以对矩阵执行若干次操作。每次操作中，你可任选一个整数 $k$，然后对每个下标 $i$（$1 \leq i \leq n$），交换 $A_{i, k}$ 与 $A_{k, i}$。注意，元素 $A_{k, k}$ 保持不变。

例如，当 $n = 4$ 且 $k = 3$ 时，该矩阵将按如下方式变换：

操作 $k = 3$ 将蓝色行与绿色列互换。

你可以执行该操作任意多次。求经过任意次操作后所能得到的字典序最小的矩阵$^\dagger$。

${}^\dagger$ 对于两个 $n \times n$ 矩阵 $A$ 和 $B$，定义 $a_{(i-1) \cdot n + j} = A_{i,j}$，$b_{(i-1) \cdot n + j} = B_{i,j}$。则称矩阵 $A$ 字典序小于矩阵 $B$，当且仅当存在某个下标 $i$（$1 \leq i \leq n^2$），使得 $a_i \lt b_i$，且对所有满足 $1 \leq j \lt i$ 的下标 $j$，均有 $a_j = b_j$。

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 1000$) — the size of the matrix.

The $i$-th line of the next $n$ lines contains $n$ integers $A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$ ($1 \le A_{i, j} \le 10^9$) — description of the matrix $A$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^6$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 1000$）—— 矩阵的大小。

接下来 $n$ 行中的第 $i$ 行包含 $n$ 个整数 $A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$（$1 \le A_{i, j} \le 10^9$）—— 矩阵 $A$ 的描述。

保证所有测试用例的 $n^2$ 之和不超过 $10^6$。

For each test case, print $n$ lines with $n$ integers each — the lexicographically smallest matrix.

对于每个测试用例，输出 $n$ 行，每行包含 $n$ 个整数——即字典序最小的矩阵。

Note that in every picture below the matrix is transformed in such a way that the blue rows are swapped with the green columns.

In the first test case, we can perform $1$ operation for $k = 3$. The matrix will be transformed as below:

In the second test case, we can perform $2$ operations for $k = 1$ and $k = 3$:

注意：在下方每张图中，矩阵均经过变换，使得蓝色行与绿色列互换。

在第一个测试用例中，我们可以对 $k = 3$ 执行 $1$ 次操作。矩阵将按如下方式变换：

在第二个测试用例中，我们可以分别对 $k = 1$ 和 $k = 3$ 各执行 $1$ 次操作，共 $2$ 次操作：