Siu przygotował deser z kasztanów (bamyang-gaeng) w kształcie siatki o wymiarach $N \times N$. Każde pole deseru ma przypisaną unikalną rangę będącą liczbą całkowitą z zakresu od $1$ do $N^2$. Teraz chce pokroić deser na małe kawałki, aby rozdać je uczestnikom UCPC. Każdy kawałek deseru składa się z dwóch sąsiadujących ze sobą pól (w pionie lub poziomie), a ranga kawałka jest równa wyższej z rang pól, z których się składa. Ponieważ im niższa ranga kawałka, tym smaczniejszy jest deser, Siu chce pokroić deser tak, aby zminimalizować maksymalną rangę wśród wszystkich kawałków, tak aby żaden z uczestników nie otrzymał niesmacznego kawałka.

Siu zapomniał jednak, ilu uczestników weźmie udział w tegorocznym UCPC! Na szczęście przygotował deser tak, aby można było rozdzielić kawałki między dowolną liczbę uczestników, ale przed rozpoczęciem zawodów zabrakło mu czasu na pokrojenie i rozdanie deseru. Dlatego Siu postanowił znaleźć optymalny sposób krojenia deseru dla każdej możliwej liczby uczestników.

Dla każdej liczby całkowitej $i$ od $1$ do $N^2/2$, wyznacz minimalną możliwą wartość maksymalnej rangi kawałka, jeśli deser zostanie pokrojony tak, aby rozdzielić kawałki między $i$ uczestników.

Wejście

W pierwszej linii podana jest długość boku deseru $N$ ($2 \le N \le 100$; $N$ jest liczbą parzystą).

Od drugiej linii następuje $N$ linii, z których każda zawiera $N$ liczb całkowitych oddzielonych spacjami. $j$-ta liczba w $(i+1)$-szej linii, $a_{ij}$, oznacza rangę pola znajdującego się w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej ($1 \le a_{ij} \le N^2$; wszystkie $a_{ij}$ są różne).

Wyjście

Wypisz $N^2/2$ linii, gdzie w $i$-tej linii znajduje się minimalna wartość maksymalnej rangi kawałka przy krojeniu deseru dla $i$ uczestników.

Przykład

Wejście 1

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

Wyjście 1

3
4
7
8
10
14
15
16

Wejście 2

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

Wyjście 2

3
4
7
8
10
14
15
16