Bessie 有一张 $N\times N$（$1\le N\le 1000$）加法表，对于所有 $1\le r,c\le N$，第 $r$ 行、第 $c$ 列的整数是 $r+c$。例如 $N=3$ 时，表如下：

2 3 4
3 4 5
4 5 6

遗憾的是，Elsie 拿到了表，通过任意多次执行下列三类操作把它打乱。

1. 交换两行

2. 交换两列

3. 选择表中都存在的两个值 $a$ 和 $b$，同时把每个 $a$ 改为 $b$，每个 $b$ 改为 $a$。

Elsie 总是按类型递增顺序操作：先执行任意多次（可以零次）类型 $1$，再执行类型 $2$，最后执行类型 $3$。

帮助 Bessie 恢复 Elsie 执行完全部类型 $1$、$2$ 操作，但尚未执行任何类型 $3$ 操作时，表的一个可能状态。若有多个答案，输出字典序最小的。

比较两张表的字典序时，按自然顺序读取（行从上到下，每行从左到右），比较第一个不同的元素。

输入格式

第一行包含 $N$。

接下来 $N$ 行各包含 $N$ 个整数，表示被 Elsie 打乱后的加法表。

输出格式

输出全部类型 1、2 操作后、任何类型 3 操作前，字典序最小的可能状态。保证答案存在。

样例

输入格式 1

1
2

输出格式 1

2

说明

无论 Elsie 如何操作，表都不会改变。

输入格式 2

3
3 4 2
5 2 3
6 3 5

输出格式 2

4 2 3
5 3 4
6 4 5

说明

以下是 Elsie 可能执行的一种操作序列。

2 3 4
3 4 5
4 5 6
-> (操作 1：交换第 2、3 列)
2 4 3
3 5 4
4 6 5
-> (操作 1：交换第 1、2 列)
4 2 3
5 3 4
6 4 5
-> (操作 3：交换值 2、3)
4 3 2
5 2 4
6 4 5
-> (操作 3：交换值 3、4)
3 4 2
5 2 3
6 3 5

注意：以下也是类型 1、2 操作后的可能状态，但不是字典序最小的，因为第一行第二个元素比正确答案的大。

4 6 5
3 5 4
2 4 3

输入格式 3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

输出格式 3

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

子任务

• 测试数据 4-5：$N\le 6$
• 测试数据 6-7：$N\le 8$
• 测试数据 8-11：$N\le 100$
• 测试数据 12-15：无额外限制。

题目作者：Benjamin Qi