Siu a préparé un « bamyang-gaeng » (gelée de châtaigne) en forme de grille de taille $N \times N$. Chaque case de la grille est marquée par un grade, représenté par un entier distinct compris entre $1$ et $N^2$. Il souhaite maintenant découper ce bamyang-gaeng en petits morceaux pour les distribuer aux participants de l'UCPC. Un morceau de bamyang-gaeng est constitué de deux cases adjacentes horizontalement ou verticalement, et le grade d'un morceau est défini par le grade le plus élevé parmi les deux cases qui le composent. Comme un morceau est d'autant plus savoureux que son grade est faible, Siu souhaite découper le bamyang-gaeng de manière à minimiser le grade du morceau le plus élevé, afin qu'aucun participant ne reçoive un morceau de mauvaise qualité.

Cependant, Siu a oublié combien de participants sont présents à l'UCPC ! Heureusement, il a préparé le bamyang-gaeng de manière à ce qu'il puisse être distribué à n'importe quel nombre de participants, mais il manque de temps pour le découper avant le début de la compétition. Il décide donc de trouver la méthode de découpe optimale pour chaque nombre possible de participants.

Pour chaque entier $i$ compris entre $1$ et $N^2/2$, calculez la valeur minimale du grade du morceau le plus élevé lorsque le bamyang-gaeng est découpé pour être distribué à $i$ participants.

Entrée

La première ligne contient la longueur d'un côté du bamyang-gaeng, $N$. ($2 \le N \le 100$ ; $N$ est pair).

À partir de la deuxième ligne, $N$ lignes sont données, chacune contenant $N$ entiers séparés par des espaces. Le $j$-ième entier de la $(i+1)$-ième ligne, $a_{ij}$, représente le grade de la case située à la $i$-ième ligne et à la $j$-ième colonne du bamyang-gaeng. ($1 \le a_{ij} \le N^2$ ; les $a_{ij}$ sont tous distincts).

Sortie

Sur $N^2/2$ lignes, affichez à la $i$-ième ligne la valeur minimale du grade du morceau le plus élevé lorsque le bamyang-gaeng est découpé pour être distribué à $i$ participants.

Exemples

Entrée 1

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

Sortie 1

3
4
7
8
10
14
15
16

Entrée 2

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

Sortie 2

3
4
7
8
10
14
15
16