Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Restore Magic Rectangle

By ovis96 · Limits 1s, 512 MB · Custom Checker

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.

Sample

InputOutput
1
2 2
2 2
3 4
2 3
4 2

Note: Use Faster I/O.

    Discussion

    Statistics


    21% Solution Ratio

    NirjhorEarliest, 1M ago

    YouKnowWhoFastest, 0.4s

    YouKnowWhoLightest, 18 MB

    YouKnowWhoShortest, 1315B

    Submit

    Login to submit