Cow Treats

The cows had another record month of milk production, so each one has earned a special treat. They stand packed into a $W \times H$ rectangular formation ($1 \le W \le 25$, $1 \le H \le 25$), waiting for their treats.

Each cow has a distinct figure of merit $F_{rc}$ ($1 \le F_{rc} \le 1{,}000{,}000$) describing her overall milk production. Farmer John wants to reward the best producers first. He hands out treats one row at a time: he walks along row 1 from its first column to its last, giving every cow in row 1 a treat, then moves on to row 2, and so on. So the order in which treats are handed out is:

1    2    3   ...  W
W+1  W+2  W+3 ...  2W
...

Farmer John asks the cows to rearrange themselves so that better producers are served earlier. The cows cannot sort themselves freely; the only moves they may make are to swap two entire rows or swap two entire columns of the formation. Using just these moves they do their best, placing the highest-rated cow in the upper-left corner (row 1, column 1), the next-highest as early as possible, and so on, following this greedy rule:

• Find the highest-rated cow. Swap rows and columns until she sits at row 1, column 1, then fix her there so she never moves again.
• Repeat until no more cows can be improved: take the next highest-rated cow that is not yet fixed and, without moving any already-fixed higher-rated cow, swap rows and/or columns to bring her to the earliest still-reachable slot (for example row 1, column 2 if it is reachable, otherwise row 2, column 1, and so on). Once she reaches that slot, fix her there; her row and column can no longer be swapped.

A cow can move only while neither her current row nor her current column has been fixed. If only her row is fixed she may still change columns (staying in that row); if only her column is fixed she may still change rows; if both are fixed she cannot move at all.

Worked example (3 rows, 4 columns):

5  7  4  1
9 99  2  6
8  3 10 11

The cow rated 99 is the best and belongs in the upper-left corner. Swapping rows 1 and 2 and then columns 1 and 2 gives:

99  9  2  6
 7  5  4  1
 3  8 10 11

The cow rated 11 should be served as soon as possible after her. She is at slot (3, 4), the very last one, so it is already too late to reach row 1 or even column 1; the best she can do is (2, 2). Swapping columns 2 and 4 and then rows 2 and 3:

Swap columns 2 and 4    Swap rows 2 and 3
99   6  2  9            99   6  2  9
 7   1  4  5      ->     3  11 10  8
 3  11 10  8            7   1  4  5

The cow rated 10 is fixed right where she is, just after 11. Cow 9 is already served. Cow 8 comes just after 10, and cow 7 just after 8. Cow 6 is already served. Cow 5 would like to reach row 3, column 2, but rows 1 and 2 and all columns are already fixed, so she - like cows 1 and 4 - cannot move. The formation above is therefore the best the cows can achieve.

Given the starting formation, output the final formation the cows reach with this greedy procedure.

• Line 1: two space-separated integers $W$ and $H$.
• Lines 2 to $H+1$: line $i+1$ contains $W$ space-separated integers, the values $F_{ic}$ for columns $c = 1 \dots W$ of row $i$.

• Lines 1 to $H$: line $i$ contains $W$ space-separated integers, the $i$-th row of the cows' final formation.