Bessie có bảng cộng $N\times N$ ($1\le N\le 1000$), trong đó số ở hàng $r$, cột $c$ là $r+c$ với mọi $1\le r,c\le N$. Ví dụ khi $N=3$:

2 3 4
3 4 5
4 5 6

Tiếc thay, Elsie lấy bảng và hoán vị bằng cách thực hiện tùy ý nhiều lần ba loại thao tác sau.

1. Đổi hai hàng

2. Đổi hai cột

3. Chọn hai giá trị $a$ và $b$ đều có trong bảng, rồi đồng thời đổi mọi $a$ thành $b$ và mọi $b$ thành $a$.

Các loại luôn được thực hiện tăng dần: tùy ý nhiều lần (có thể không lần nào) loại $1$, rồi loại $2$, cuối cùng loại $3$.

Khôi phục một trạng thái có thể sau tất cả thao tác loại $1$ và $2$, nhưng trước bất kỳ thao tác loại $3$ nào. Nếu có nhiều đáp án, in trạng thái nhỏ nhất từ điển.

Để so sánh hai bảng theo thứ tự từ điển, đọc theo thứ tự tự nhiên (hàng từ trên xuống, trong hàng từ trái sang phải), rồi so sánh ô khác nhau đầu tiên.

Dữ liệu vào

Dòng đầu chứa $N$.

$N$ dòng tiếp theo mỗi dòng chứa $N$ số nguyên, bảng cộng sau khi Elsie hoán vị.

Dữ liệu ra

In trạng thái có thể nhỏ nhất từ điển sau mọi thao tác loại 1 và 2 nhưng trước loại 3. Đảm bảo đáp án tồn tại.

Ví dụ

Dữ liệu vào 1

1
2

Dữ liệu ra 1

2

Ghi chú

Dù Elsie thực hiện gì, bảng không đổi.

Dữ liệu vào 2

3
3 4 2
5 2 3
6 3 5

Dữ liệu ra 2

4 2 3
5 3 4
6 4 5

Ghi chú

Sau đây là một chuỗi thao tác có thể của Elsie.

2 3 4
3 4 5
4 5 6
-> (thao tác 1: đổi cột 2 và 3)
2 4 3
3 5 4
4 6 5
-> (thao tác 1: đổi cột 1 và 2)
4 2 3
5 3 4
6 4 5
-> (thao tác 3: đổi giá trị 2 và 3)
4 3 2
5 2 4
6 4 5
-> (thao tác 3: đổi giá trị 3 và 4)
3 4 2
5 2 3
6 3 5

Lưu ý: trạng thái dưới cũng có thể sau loại 1 và 2, nhưng không nhỏ nhất từ điển vì ô thứ hai của hàng đầu lớn hơn trong đáp án đúng.

4 6 5
3 5 4
2 4 3

Dữ liệu vào 3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

Dữ liệu ra 3

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

Nhiệm vụ con

• Dữ liệu vào 4-5: $N\le 6$
• Dữ liệu vào 6-7: $N\le 8$
• Dữ liệu vào 8-11: $N\le 100$
• Dữ liệu vào 12-15: không có hạn chế bổ sung.

Tác giả bài toán: Benjamin Qi