Siu ha preparado un "bamyang-gaeng" (gelatina de castañas) con forma de cuadrícula de $N \times N$. Cada celda de la cuadrícula tiene asignada una calificación con un número entero distinto entre $1$ y $N^2$. Ahora, desea cortar esta gelatina en trozos pequeños para repartirlos entre los participantes de la UCPC. Un trozo de gelatina consiste en dos celdas adyacentes (ya sea vertical u horizontalmente), y la calificación de un trozo se define como la mayor de las calificaciones de las dos celdas que lo componen. Dado que una gelatina es más deliciosa cuanto menor es su calificación, Siu quiere cortar la gelatina de tal manera que la calificación máxima entre todos los trozos sea la mínima posible, para evitar que algún participante reciba un trozo poco delicioso.

Sin embargo, ¡Siu ha olvidado cuántos participantes asistirán a la UCPC! Afortunadamente, preparó la gelatina de modo que pueda repartirse entre cualquier número de participantes, pero no tiene tiempo suficiente para cortarla antes de que comience el concurso. Por lo tanto, Siu ha decidido encontrar la forma óptima de cortar la gelatina para cada posible número de participantes.

Para cada número entero $i$ desde $1$ hasta $N^2/2$, calcule el valor mínimo de la calificación máxima de un trozo al cortar la gelatina para repartirla entre $i$ participantes.

Entrada

La primera línea contiene la longitud de un lado de la cuadrícula, $N$. ($2 \le N \le 100$; $N$ es un número par).

A partir de la segunda línea, se proporcionan $N$ líneas, cada una con $N$ números enteros separados por espacios. El $j$-ésimo entero de la línea $(i+1)$ representa la calificación $a_{ij}$ de la celda en la $i$-ésima fila y $j$-ésima columna desde arriba. ($1 \le a_{ij} \le N^2$; todos los $a_{ij}$ son distintos).

Salida

Imprima $N^2/2$ líneas, donde la $i$-ésima línea contiene el valor mínimo de la calificación máxima de un trozo al cortar la gelatina para repartirla entre $i$ participantes.

Ejemplos

Entrada 1

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

Salida 1

3
4
7
8
10
14
15
16

Entrada 2

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

Salida 2

3
4
7
8
10
14
15
16