Cross Swapping
Description
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 swaps the blue row with the green column.
You can perform this operation any number of times. Find the lexicographically smallest matrix you can obtain after performing arbitrary number of operations.
For two matrices and of size , let and . Then, the matrix is lexicographically smaller than the matrix when there exists an index () such that a_i < b_i and for all indices such that 1 \leq j < i, .
给定一个 的矩阵。一次操作可以给定一个 然后交换所有的 和 。
如图表示 的情况。
求若干次操作后字典序最小的矩阵。
Input
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$.
Output
For each test case, print $n$ lines with $n$ integers each — the lexicographically smallest matrix.
2
3
2 1 2
2 1 2
1 1 2
4
3 3 1 2
1 1 3 1
3 2 3 2
2 3 3 1
2 1 1
2 1 1
2 2 2
3 1 1 2
3 1 2 1
3 3 3 3
2 3 2 1
Note
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:
