Problem Description

Mikhail decided to learn generalized chess, so he prepared a board of size $n \times n$. He painted the cell in row $i$ and column $j$ with color $a_{i j}$.

Since Mikhail is a beginner, he may have painted the board incorrectly. Therefore, some cells on the board may need to be repainted to another color. A board is called properly colored if and only if it satisfies both of the following conditions:

• The board uses at most two different colors in total.
• There are no edge-adjacent cells with the same color.

Mikhail also considers that playing on a board that is too large would be too difficult. Therefore, he may cut out a smaller board from his board, that is, keep the rectangle formed by the first $r$ rows and the first $c$ columns, and only make this part properly colored.

For every pair $(r, c)$ ($1 \le r \le n$, $1 \le c \le n$), compute the value $b_{r c}$—the minimum number of cells Mikhail needs to repaint so that the rectangle formed by the first $r$ rows and the first $c$ columns becomes properly colored.

Input Format

The first line contains an integer $n$ ($1 \le n \le 400$), which denotes the size of the board.

The next $n$ lines describe the board: the $i$-th line contains $n$ integers $a_{i 1}, \ldots, a_{i n}$ ($1 \le a_{i j} \le 10^9$), representing the colors of the cells in row $i$ of the board.

Output Format

Output $n$ lines, where the $i$-th line should contain $n$ integers $b_{i 1}, \ldots, b_{i n}$.

2
7 7
7 7

0 1
1 2

3
1 1 2
2 4 4
3 1 2

0 1 1
0 2 4
1 3 5

Hint

Subtasks

Translated by DeepSeek V4 Pro.

Translated by ChatGPT 5