Siu đã làm một chiếc bánh hạt dẻ (bamyanggaeng) hình lưới kích thước $N \times N$. Mỗi ô của chiếc bánh được đánh số thứ tự từ $1$ đến $N^2$ với các giá trị khác nhau. Giờ đây, Siu muốn cắt chiếc bánh này thành các miếng nhỏ để chia cho những người tham gia UCPC. Mỗi miếng bánh bao gồm hai ô kề nhau theo chiều dọc hoặc chiều ngang, và cấp độ của một miếng bánh được xác định bằng giá trị lớn hơn trong hai ô tạo nên miếng bánh đó. Vì miếng bánh có cấp độ càng nhỏ thì càng ngon, Siu muốn cắt bánh sao cho giá trị lớn nhất trong số các cấp độ của các miếng bánh là nhỏ nhất có thể, để không người tham gia nào phải nhận miếng bánh "dở".

Tuy nhiên, Siu đã quên mất số lượng người tham gia UCPC năm nay! May mắn thay, chiếc bánh đã được làm đủ để chia cho tất cả mọi người, nhưng Siu không có đủ thời gian để cắt bánh trước khi cuộc thi bắt đầu. Vì vậy, Siu quyết định tìm cách cắt bánh tối ưu cho mọi số lượng người tham gia có thể.

Với mỗi số nguyên $i$ từ $1$ đến $N^2/2$, hãy tìm giá trị nhỏ nhất của cấp độ miếng bánh lớn nhất khi cắt bánh để chia cho $i$ người tham gia.

Dữ liệu vào

Dòng đầu tiên chứa độ dài một cạnh của chiếc bánh $N$ ($2 \le N \le 100$; $N$ là số chẵn).

Từ dòng thứ hai trở đi, mỗi dòng chứa $N$ số nguyên cách nhau bởi dấu cách. Số nguyên thứ $j$ trên dòng thứ $(i+1)$ là $a_{ij}$, biểu thị cấp độ của ô ở hàng thứ $i$ và cột thứ $j$ từ trên xuống, từ trái sang ($1 \le a_{ij} \le N^2$; các $a_{ij}$ là khác nhau).

Dữ liệu ra

In ra $N^2/2$ dòng, trong đó dòng thứ $i$ là giá trị nhỏ nhất của cấp độ miếng bánh lớn nhất khi cắt bánh để chia cho $i$ người tham gia.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
4
7
8
10
14
15
16

Dữ liệu vào 2

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

Dữ liệu ra 2

3
4
7
8
10
14
15
16