A15359. 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 < b_i$ and for all indices $j$ such that $1 \leq j < i$ , $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$ .

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

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$ :