Random coder boy Kiny once had a rectangle (2D grid) as quarantine gift. Every random people have something like that, what is the specialty then? The main specialty of the grid is for every row and column all the values are unique.

More formally suppose the grid size is $n \times m$, which means the grid has $n$ rows and $m$ columns. For every row i, 1 ≤ i ≤ n, let $R_i$ is the set of all values in the row i then $|R_i|$ = m (size of $R_i$ is m). Similarly, for every column j, 1 ≤ j ≤ m, let $C_j$ is the set of all values in the column j then $|C_j|$ = n.

But this was Kiny's rectangle before last night. Yesterday night, Kiny suddenly woke up by the barking of the street dog near his house. He assumes that someone (thief) entered his room and shuffled his rectangle. So that the order of the rectangle is not the same as before. For this, the main specialty of the grid might be lost. But he is desperate to have its specialty back. So he came to you to solve his problem.

Input

The first line will contain T ( number of test cases, T ≤ $10$ ). For each test case there will be n m ( which means the grid has n rows and m colums, $n \times m$ ≤ $10^5$ ) and for following n lines, each will contain m numbers (1 ≤ each number ≤ $10^9$ ) describing the grid. As mentioned earlier in the problem, this grid might have lost its speciality.

Output

For each test case output n lines, for each n lines there will be m integers which indicates the special rectangle. There can be multiple possible solutions, any of them would be enough.