```

Time Limit: 3000 MS    Memory Limit: 65536 K

Description

The cows celebrated another banner month for record milk production
and thus have each earned a special treat. They completely fill a
W x H rectangle formation (1 <= W <= 25; 1 <= H <= 25) awaiting
their treat.

Each cow has a unique figure of merit F_rc (1 <= F_rc <= 1,000,000)
which denotes her overall milk production performance. Farmer John
thinks it is only fair to prioritize the treats handed out, rewarding
the highest producing cows first. He plans to traverse the rectangular
formation one row at a time, starting at the beginning of row 1 and
giving out all row 1's treats before he starts on row 2 using the
same method.

He has asked the cows to reorganize themselves so that the cows
with better production are rewarded first. The cows, though, are
not so very good at organization. They can either swap a pair of
rows or swap a pair of columns of their formation. FJ has asked
them to do the best they can by moving the best cow to the upper
left corner (row 1, column 1), the next best cow to row 1, column
2 (if possible), and so on. Of course, the cows can not fully sort
themselves, but they can do their best by following this heuristic:

* determine the order of FJ's treat awards:
1    2   3  ...
W+1 W+2 W+3 ...

* find the highest rated cow; swap rows and columns until she
is at row 1, column 1; never move her again

* Then execute this rule until as many cows are placed as possible:

Find the next highest rated cow. Swap rows and columns
(without moving any higher-rated cow) to move her to the
best possible spot that is still available (e.g., row 1,
column 2 if it's available of row 2, column 1 if no slots
can be achieved in row 1.

By way of example, consider this set of 3 x 4 cows:

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

The cow with 99 is clearly the highest-rated and belows in the upper
left corner. Swap rows 1 and 2 then swap columns 1 and 2 (or do it
the other way around -- the answer is the same):

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

The cow with 11 should be rewarded as soon as possible after the
highest-rated cow. She is current in slot (3,4), the last slot to
be rewarded. At this point, it's too late to swap her into the first
row or even the first column. Thus, she needs to move to (2,2) by
swapping columns 2 and 4 then swapping rows 2 and 3:

Swap cols 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 with 10 is rewarded directly after the cow with 11.  The
cow 9 is already rewarded. The cow with 8 is awarded just after the
cow with 10. The cow with 7 is rewarded directly after the cow with
8.  The cow with 6 is already rewarded. The cow with 5 would best
move to row 3, column 2 but the rows 1 and 2 are frozen as are all
the columns.  Thus, cows 1, 4, and 5 do not move, and the second
diagram above is the "best the cows can do".

Implement this algorithm for other rectangular arrays of cows.

Input

* Line 1: Two space-separated integers: W and H

* Lines 2..H+1: Line i+1 contains W space-separated integers F_ic,
where c ranges from 1 to W.

Output

* Lines 1..H: Line i contains W space-separated integers representing
the i-th row of cows in the cows' final formation.

Sample Input

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

Sample Output

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

Source
usaco FEB11

```