시우는 $N \times N$ 크기의 격자 모양 밤양갱을 만들었다. 밤양갱의 각 칸에는 $1$ 이상 $N^2$ 이하의 서로 다른 정수로 등급이 매겨져 있다. 이제 이 밤양갱을 작은 조각으로 잘라 UCPC 참가자들에게 나누어 주려 한다. 이때 하나의 밤양갱 조각은 상하 또는 좌우로 인접한 두 개의 칸으로 이루어지며, 밤양갱 조각의 등급은 그 조각을 이루는 칸의 등급 중 더 큰 쪽을 따른다. 조각의 등급이 작을수록 맛있는 밤양갱이 되기 때문에, 시우는 어떤 참가자들이 맛없는 밤양갱 조각을 받는 일이 없도록 가장 등급이 큰 밤양갱 조각의 등급이 최소가 되도록 밤양갱을 자르려 한다.

그러나 시우는 이번 UCPC의 참가자가 몇 명인지 까먹고 말았다! 다행히 모든 참가자에게 밤양갱 조각을 나누어줄 수 있도록 밤양갱을 만들긴 했지만, 대회 시작 전까지 밤양갱을 잘라 나누어 주기에 시간이 부족했다. 그래서 시우는 밤양갱을 나누어줄 수 있는 모든 참가자 수마다 밤양갱을 자르는 최적의 방법을 찾기로 했다.

$1$ 이상 $N^2/2$ 이하의 모든 정수 $i$에 대해, $i$명의 참가자에게 밤양갱 조각을 나누어줄 수 있도록 밤양갱을 자를 때 가장 등급이 큰 밤양갱 조각의 등급의 최솟값을 구하시오.

Input

첫 줄에 밤양갱의 한 변의 길이 $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}$는 서로 다르다.)

Output

$N^2/2$개의 줄에 걸쳐, $i$번째 줄에 $i$명의 참가자에게 밤양갱 조각을 나누어줄 수 있도록 밤양갱을 자를 때 가장 등급이 큰 밤양갱 조각의 등급의 최솟값을 출력한다.

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