シウは $N \times N$ の格子状の栗羊羹を作った。栗羊羹の各マスには $1$ 以上 $N^2$ 以下の互いに異なる整数で等級が付けられている。今、この栗羊羹を小さなピースに切り分けてUCPCの参加者に配ろうとしている。ここで、栗羊羹の1つのピースは上下または左右に隣接する2つのマスからなり、栗羊羹のピースの等級は、そのピースを構成するマスの等級のうち大きい方に従う。ピースの等級が小さいほど美味しい栗羊羹となるため、シウは参加者が美味しくない栗羊羹のピースを受け取ることがないよう、最も等級が大きい栗羊羹のピースの等級が最小になるように栗羊羹を切り分けようとしている。

しかし、シウは今回のUCPCの参加者が何人か忘れてしまった！幸い、すべての参加者に栗羊羹のピースを配れるように栗羊羹は作ってあるが、大会開始までに栗羊羹を切り分けて配るには時間が足りなかった。そこでシウは、栗羊羹を配ることができるすべての参加者数について、栗羊羹を切り分ける最適な方法を見つけることにした。

$1$ 以上 $N^2/2$ 以下のすべての整数 $i$ について、$i$ 人の参加者に栗羊羹のピースを配れるように切り分ける際、最も等級が大きい栗羊羹のピースの等級の最小値を求めよ。

入力

1行目に栗羊羹の1辺の長さ $N$ が与えられる。($2 \le N \le 100$; $N$ は偶数)

2行目から $N$ 行にわたって、各行に $N$ 個の整数が空白区切りで与えられる。$(i+1)$ 行目の $j$ 番目の整数 $a_{ij}$ は、栗羊羹の上から $i$ 番目、左から $j$ 番目のマスの等級を意味する。($1 \le a_{ij} \le N^2$; $a_{ij}$ は互いに異なる。)

出力

$N^2/2$ 行にわたって、$i$ 行目に $i$ 人の参加者に栗羊羹のピースを配れるように切り分ける際、最も等級が大きい栗羊羹のピースの等級の最小値を出力する。

入出力例

入力 1

4
6 2 3 7
16 9 10 12
1 15 11 14
4 5 8 13

出力 1

3
4
7
8
10
14
15
16

入力 2

4
6 2 3 7
16 9 10 12
1 15 11 14
4 5 8 13

出力 2

3
4
7
8
10
14
15
16