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