B. 矩阵字典序

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

Problem B. 矩阵字典序

题目英文名:matrix

时空限制:1s/256MB

题目描述:

有一个的二维矩阵,你可以进行任意次(包括次)操作,每次操作选择一个整数满足,交换第行和第列。具体来说,对于和你选定的,交换和。

你希望经过若干次操作以后,这个矩阵的字典序变得尽可能小。矩阵的字典序是将矩阵按行的顺序展开成一个长度为的一维数组后的字典序。换句话说,你希望矩阵的第一行第一个元素最小;在此基础上,第一行第二个元素最小;……;在此基础上,第一行第个元素最小;在此基础上,第二行第一个元素最小;……

给定初始矩阵,请你决定进行哪些操作,使得操作后的矩阵字典序尽可能小。输出操作后的矩阵即可。

输入格式

输入格式:

第一行输入正整数

接下来行,每行输入个用空格隔开的正整数,表示矩阵

矩阵中可能有相同的数字

输出格式

输出格式:

输出行,每行个用空格隔开的正整数,表示操作后的矩阵

样例

输入样例:

3
1 4 7
2 5 6
3 8 9

输出样例:

1 2 3
4 5 6
7 8 9

样例解释:

操作了两次,分别选择了和,操作后的矩阵字典序为显然是最小的

数据范围与提示

数据范围:

对于30%的数据,

对于60%的数据,

对于100%的数据,