Siwoo 制作了一个 $N \times N$ 大小的网格状栗子羊羹。羊羹的每个格子都被赋予了一个 $1$ 到 $N^2$ 之间互不相同的整数等级。现在他打算将这块羊羹切成小块分给 UCPC 的参赛者。每个羊羹碎片由两个上下或左右相邻的格子组成，碎片的等级取组成该碎片的两个格子中等级较大者的值。由于碎片的等级越小，羊羹就越美味，Siwoo 希望通过切割方式，使得所有碎片中等级最高的那块碎片的等级尽可能小，从而避免参赛者拿到不好吃的羊羹。

然而，Siwoo 忘记了这次 UCPC 的参赛人数！幸运的是，他制作的羊羹足够分给所有参赛者，但由于距离比赛开始时间紧迫，他无法在赛前切好羊羹。因此，Siwoo 决定针对每一种可能的参赛人数，找出切分羊羹的最优方案。

对于所有 $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$ 名参赛者时，等级最高的羊羹碎片的等级最小值。

样例

输入 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