Сиу приготовил бамьян-гэн (корейское лакомство из каштанов) в форме сетки размером $N \times N$. Каждая ячейка бамьян-гэна имеет уникальный рейтинг — целое число от $1$ до $N^2$. Теперь он хочет разрезать этот бамьян-гэн на маленькие кусочки, чтобы раздать их участникам UCPC. Каждый кусочек бамьян-гэна состоит из двух ячеек, соседствующих по вертикали или горизонтали, а рейтинг кусочка определяется как максимальный из рейтингов двух ячеек, из которых он состоит. Поскольку чем меньше рейтинг кусочка, тем он вкуснее, Сиу хочет разрезать бамьян-гэн так, чтобы минимизировать максимальный рейтинг среди всех полученных кусочков, чтобы никто из участников не получил невкусный кусочек.

Однако Сиу забыл, сколько участников будет на этом UCPC! К счастью, он приготовил бамьян-гэн так, чтобы его можно было разделить на кусочки для любого количества участников, но у него не хватает времени нарезать его до начала соревнования. Поэтому Сиу решил найти оптимальный способ нарезки для каждого возможного количества участников.

Для каждого целого числа $i$ от $1$ до $N^2/2$ найдите минимально возможное значение максимального рейтинга кусочка при нарезке бамьян-гэна на $i$ кусочков для $i$ участников.

Входные данные

В первой строке задана длина стороны бамьян-гэна $N$ ($2 \le N \le 100$; $N$ — четное число).

Со второй строки заданы $N$ строк, каждая из которых содержит $N$ целых чисел, разделенных пробелами. $j$-е число в $(i+1)$-й строке $a_{ij}$ обозначает рейтинг ячейки, находящейся в $i$-й строке сверху и $j$-м столбце слева ($1 \le a_{ij} \le N^2$; все $a_{ij}$ различны).

Выходные данные

Выведите $N^2/2$ строк. В $i$-й строке выведите минимально возможное значение максимального рейтинга кусочка при нарезке бамьян-гэна на $i$ кусочков.

Примеры

Входные данные 1

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

Выходные данные 1

3
4
7
8
10
14
15
16

Входные данные 2

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

Выходные данные 2

3
4
7
8
10
14
15
16