# [Solution] Cross Swapping solution codeforces

Cross Swapping solution codeforces – You are given a square matrix 𝐴A of size 𝑛×𝑛n×n whose elements are integers. We will denote the element on the intersection of the 𝑖i-th row and the 𝑗j-th column as 𝐴𝑖,𝑗Ai,j.

## [Solution] Cross Swapping solution codeforces

You can perform operations on the matrix. In each operation, you can choose an integer 𝑘k, then for each index 𝑖i (1𝑖𝑛1≤i≤n), swap 𝐴𝑖,𝑘Ai,k with 𝐴𝑘,𝑖Ak,i. Note that cell 𝐴𝑘,𝑘Ak,k remains unchanged.

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

The operation 𝑘=3k=3 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 𝐴A and 𝐵B of size 𝑛×𝑛n×n, let 𝑎(𝑖1)𝑛+𝑗=𝐴𝑖,𝑗a(i−1)⋅n+j=Ai,j and 𝑏(𝑖1)𝑛+𝑗=𝐵𝑖,𝑗b(i−1)⋅n+j=Bi,j. Then, the matrix 𝐴A is lexicographically smaller than the matrix 𝐵B when there exists an index 𝑖i (1𝑖𝑛21≤i≤n2) such that 𝑎𝑖<𝑏𝑖ai<bi and for all indices 𝑗j such that 1𝑗<𝑖1≤j<i𝑎𝑗=𝑏𝑗aj=bj.

## [Solution] Cross Swapping solution codeforces

The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛10001≤n≤1000) — the size of the matrix.

The 𝑖i-th line of the next 𝑛n lines contains 𝑛n integers 𝐴𝑖,1,𝐴𝑖,2,,𝐴𝑖,𝑛Ai,1,Ai,2,…,Ai,n (1𝐴𝑖,𝑗1091≤Ai,j≤109) — description of the matrix 𝐴A.

It is guaranteed that the sum of 𝑛2n2 over all test cases does not exceed 106106.

Output

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

Example
input

Copy
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

output

Copy
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


## [Solution] Cross Swapping solution codeforces

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 11 operation for 𝑘=3k=3. The matrix will be transformed as below:

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