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

99 6 2 9

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

1. 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

Output

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