Siwoo 製作了一個 $N \times N$ 大小的網格狀栗子羊羹。羊羹的每個格子都被標記了 $1$ 到 $N^2$ 之間互不相同的整數作為等級。現在他打算將這塊羊羹切成小塊，分給 UCPC 的參賽者。每一塊羊羹由上下或左右相鄰的兩個格子組成，而羊羹塊的等級取決於組成該塊的兩個格子中等級較大者。由於等級越小的羊羹塊越美味，Siwoo 希望透過切割方式，使得所有羊羹塊中等級最高的那一塊，其等級達到最小，以確保沒有參賽者會拿到不好吃的羊羹塊。

然而，Siwoo 忘記了這次 UCPC 到底有多少位參賽者！幸運的是，他製作的羊羹足夠分給所有參賽者，但由於比賽開始前時間緊迫，他無法在當下才進行切割。因此，Siwoo 決定針對所有可能的參賽人數，分別找出切割羊羹的最佳方案。

對於所有 $1$ 到 $N^2/2$ 之間的整數 $i$，請計算當將羊羹切成 $i$ 塊以分給 $i$ 位參賽者時，所有羊羹塊中等級最高的那一塊，其等級的最小值。

輸入格式

第一行給出羊羹的邊長 $N$。($2 \le N \le 100$; $N$ 為偶數)

從第二行開始的 $N$ 行中，每行給出 $N$ 個以空格分隔的整數。第 $(i+1)$ 行的第 $j$ 個整數 $a_{ij}$ 代表羊羹從上往下數第 $i$ 行、從左往右數第 $j$ 列的格子等級。($1 \le a_{ij} \le N^2$; $a_{ij}$ 皆不相同。)

輸出格式

輸出 $N^2/2$ 行，第 $i$ 行輸出當將羊羹切成 $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