Mikhail quyết định học chơi cờ tổng quát hóa. Vì vậy, anh ấy đã chuẩn bị một bàn cờ kích thước $n \times n$ ô. Mỗi ô tại giao điểm của hàng $i$ và cột $j$ được tô màu với màu $a_{ij}$.

Mikhail là một người chơi mới bắt đầu và có thể đã tô màu bàn cờ không chính xác. Do đó, một số ô trên bàn cờ có thể cần được sơn lại. Bàn cờ được coi là tô màu đúng nếu hai điều kiện sau được thỏa mãn:

• Các ô trên bàn cờ được tô bằng không quá hai màu phân biệt.
• Không có hai ô kề cạnh (cùng chung một cạnh) nào được tô cùng một màu.

Mikhail nhận ra rằng chơi trên một bàn cờ lớn sẽ quá khó đối với anh ấy. Do đó, anh ấy có thể cắt ra một bàn cờ nhỏ hơn từ bàn cờ của mình, để lại một vùng hình chữ nhật gồm $r$ hàng đầu tiên và $c$ cột đầu tiên, và chỉ tô màu đúng cho vùng này. Với mỗi cặp số $(r, c)$ mà $1 \le r \le n$ và $1 \le c \le n$, hãy tính giá trị $b_{rc}$ – số lượng ô tối thiểu cần sơn lại để vùng hình chữ nhật gồm $r$ hàng đầu tiên và $c$ cột đầu tiên được tô màu đúng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 400$) – kích thước của bàn cờ. $n$ dòng tiếp theo mô tả bàn cờ. Dòng thứ $i$ trong số các dòng này chứa $n$ số nguyên $a_{i1}, \dots, a_{in}$ ($1 \le a_{ij} \le 10^9$) – màu sắc của các ô trong hàng thứ $i$.

Dữ liệu ra

In ra $n$ dòng, trong đó dòng thứ $i$ chứa $n$ số nguyên $b_{i1}, \dots, b_{in}$.

Nhiệm vụ con

Ví dụ

Đầu vào 1

2
7 7
7 7

Đầu ra 1

0 1
1 2

Đầu vào 2

3
1 1 2
2 4 4
3 1 2

Đầu ra 2

0 1 1
0 2 4
1 3 5