Siu has made an $N \times N$ grid-shaped chestnut jelly (bamyanggaeng). Each cell of the chestnut jelly is assigned a unique integer grade between $1$ and $N^2$. Now, Siu wants to cut this chestnut jelly into small pieces to distribute to UCPC participants. A single piece of chestnut jelly consists of two cells that are adjacent vertically or horizontally, and the grade of a piece is defined as the maximum of the grades of the two cells that compose it. Since a piece with a lower grade is considered tastier, Siu wants to cut the chestnut jelly such that the maximum grade among all pieces is minimized, ensuring that no participant receives a "tasteless" (high-grade) piece.

However, Siu has forgotten how many participants are attending this year's UCPC! Fortunately, the chestnut jelly was made such that it can be distributed to any number of participants, but there is not enough time to cut and distribute it before the contest starts. Therefore, Siu decided to find the optimal way to cut the chestnut jelly for every possible number of participants.

For every integer $i$ from $1$ to $N^2/2$, find the minimum possible value of the maximum grade among all pieces when the chestnut jelly is cut into $i$ pieces to be distributed to $i$ participants.

Input

The first line contains the side length $N$ of the chestnut jelly. ($2 \le N \le 100$; $N$ is even)

From the second line, $N$ lines follow, each containing $N$ integers separated by spaces. The $j$-th integer on the $(i+1)$-th line, $a_{ij}$, represents the grade of the cell at the $i$-th row and $j$-th column of the chestnut jelly. ($1 \le a_{ij} \le N^2$; all $a_{ij}$ are distinct.)

Output

Output $N^2/2$ lines. The $i$-th line should contain the minimum possible value of the maximum grade among all pieces when the chestnut jelly is cut into $i$ pieces.

Examples

Input 1

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

Output 1

3
4
7
8
10
14
15
16

Input 2

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

Output 2

3
4
7
8
10
14
15
16