32122번 - 밤양갱

문제

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

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

1ドル$ 이상 $N^2/2$ 이하의 모든 정수 $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$명의 참가자에게 밤양갱 조각을 나누어줄 수 있도록 밤양갱을 자를 때 가장 등급이 큰 밤양갱 조각의 등급의 최솟값을 출력한다.

제한

힌트