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 が表を手に入れ、次の 3 種類の操作を好きな回数行って並べ替えました。
2 行を交換する
2 列を交換する
表に両方とも存在する値 $a$ と $b$ を選び、すべての $a$ を $b$ に、すべての $b$ を $a$ に同時に変える。
操作は必ず種類の昇順に行われます。まず種類 $1$ を好きな回数（0 回でも可）、次に種類 $2$、最後に種類 $3$ を行います。
種類 $1$ と $2$ の操作がすべて終わり、種類 $3$ をまだ一度も行っていない時点の表の可能な状態を復元してください。複数の答えがある場合は辞書順で最小のものを出力してください。
表の辞書順は、自然な順序（行は上から下、各行は左から右）に読んで最初に異なる要素を比較します。
入力
最初の行には $N$ が与えられます。
続く $N$ 行には各 $N$ 個の整数が与えられ、Elsie が並べ替えた後の加算表を表します。
出力
種類 1 と 2 の全操作後、種類 3 の操作前にあり得る表の辞書順最小の状態を出力してください。答えの存在は保証されます。
入出力例
入力 1
1 2
出力 1
2
注記
どんな操作をしても、表は変わりません。
入力 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 の操作後の可能な状態ですが、最初の行の 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