该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

小明写了一个程序，输入一个整数 $N$，便可以生成一个 $N×N$ 的矩阵。程序如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N;
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			cout<<i+j<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

然后他对生成的矩阵分三步依次进行了以下操作：

第一步：操作了若干次（可以为 0 次），每次操作将矩阵中的某两行进行交换；

第二步：操作了若干次（可以为 0 次），每次操作将矩阵中的某两列进行交换；

第三步：操作了若干次（可以为 0 次），每次操作选取矩阵中的某两个数进行全部互换。即，假设某次操作选取的两个数是 x, y，则将矩阵中所有的 x 替换为 y, 所有的 y 替换为 x。

注意，三步操作是依次进行的，下一步开始后，不能返回上一步进行操作。

全部操作完成后，小明向你展示了最终的矩阵。但是他已经忘了自己是如何操作的。你能帮他还原一下他可能的操作吗？

你只需要输出小明前两步操作结束之后，第三步操作开始之前，矩阵的一种可能状态。答案可能很多，你需要输出字典序最小的那个矩阵。

两个 $N × N$ 的矩阵的字典序大小关系，等于它们先按行、再按列依次比较每个元素时，第一次遇到的不同元素的大小关系。

输入格式

第一行：一个整数 $N$。

接下来是一个 $N × N$ 的矩阵，表示小明三步操作结束后的矩阵。

输出格式

一个 $N × N$ 的矩阵：共 $N$ 行，每行 $N$ 个数，同一行的数之间以一个空格隔开。数据保证有解。

样例1输入

1
2

样例1输出

2

样例2输入

3
3 6 5
6 2 4
5 4 6

样例2输出

2 4 3 
4 6 5 
3 5 4 

样例2解释

该样例中 $N = 3$

--- 初始矩阵 ---

2 3 4
3 4 5
4 5 6

--- 第一步 ---

=== 第二行和第三行交换 ===>

2 3 4
4 5 6
3 4 5

---第二步---

=== 第二列和第三列交换 ===>

2 4 3
4 6 5
3 5 4

---第三步---

=== (1) 交换 2 和 4 ===>

4 2 3
2 6 5
3 5 2

=== (2) 交换 3 和 4 ===>

3 2 4
2 6 5
4 5 2

=== (3) 交换 4 和 5 ===>

3 2 5
2 6 4
5 4 2

=== (4) 交换 2 和 6 ===>

3 6 5
6 2 4
5 4 6

至此得到小明的序列，在第三步开始之前的矩阵为：

2 4 3
4 6 5
3 5 4

是字典序最小的。

下列也是一种可能的操作序列，但在第三步开始之前的矩阵不是字典序最小的。

---初始矩阵---

2 3 4
3 4 5
4 5 6

---第一步---

=== 第一行和第三行交换 ===>

4 5 6
3 4 5
2 3 4

=== 第二行和第三行交换 ===>

4 5 6
2 3 4
3 4 5

---第二步---

=== 第一列和第二列交换 ===>

5 4 6
3 2 4
4 3 5

=== 第一列和第三列交换 ===>

6 4 5
4 2 3
5 3 4

---第三步---

=== (1) 交换 3 和 4 ===>

6 3 5
3 2 4
5 4 3

=== (2) 交换 3 和 6 ===>

3 6 5
6 2 4
5 4 6

至此得到小明的序列，在第三步开始之前的矩阵为：

6 4 5
4 2 3
5 3 4

但它不是字典序最小的。

数据范围

• 20% 的数据：$N ≤ 6$。
• 40% 的数据：$N ≤ 8$。
• 70% 的数据：$N ≤ 100$。
• 100% 的数据：$N ≤ 1000$