## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Cross Swapping Codeforces Solution

E. Cross Swapping
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ${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\le i\le 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${}^{†}$ you can obtain after performing arbitrary number of operations.

Solution Click Below:-  👉

👇👇👇👇👇

occupied

${}^{†}$ For two matrices $A$ and $B$ of size $n×n$, let ${a}_{\left(i-1\right)\cdot n+j}={A}_{i,j}$ and ${b}_{\left(i-1\right)\cdot n+j}={B}_{i,j}$. Then, the matrix $A$ is lexicographically smaller than the matrix $B$ when there exists an index $i$ ($1\le i\le {n}^{2}$) such that ${a}_{i}<{b}_{i}$ and for all indices $j$ such that $1\le j${a}_{j}={b}_{j}$.

Input

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

The first line of each test case contains a single integer $n$ ($1\le n\le 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.