喵帕斯之矩阵

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

莲酱得到了一个矩阵,不过这个矩阵特别丑,莲酱一脸嫌弃。为了让莲酱不再嫌弃这个矩阵,请你把这个矩阵变的更漂亮些。

 

比如这里有一个比较丑的矩阵

 

 

我们通过把对角线的元素进行升序排序,这个矩阵就会变得漂亮(对莲酱来说)

 

 

排序后的结果如下图

 

 

对于 n = 4 的矩阵来说要保证排序完的矩阵(a[i][j] 代表第 i 行 j 列):

a[3][1] <= a[4][2]

a[2][1] <= a[3][2] <= a[4][3]

a[1][1] <= a[2][2] <= a[3][3] <= a[4][4]

a[1][2] <= a[2][3] <= a[3][4]

a[1][3] <= a[2][4]

 

Input

多组输入直到EOF 。(保证组数小于 100)

每组数据第一行输入一个 N ,代表矩阵的列数和行数。(1 <= N <= 100)

接下来输入 N 行,每行有 N 个数 ai。(1 <= ai <= 100)

Output

每组数据输出 N 行 N 列,为排序后的矩阵。

Sample Input

4
2 7 6 8
1 2 6 9
2 6 6 21
8 9 22 3

Sample Output

2 6 6 8
1 2 7 9
2 6 3 21
8 9 22 6

Hint

Source

【2017级《程序设计基础(B)I》期末上机考试】Fish