题目描述

米哈伊尔决定学习下广义象棋，为此他准备了一个大小为 $n \times n$ 的棋盘。他将第 $i$ 行第 $j$ 列的格子涂成了颜色 $a_{i j}$。

米哈伊尔是个新手，他可能把棋盘涂错了。因此，棋盘上的某些格子可能需要重新涂成另一种颜色。一个棋盘被称为正确涂色，当且仅当同时满足以下两个条件：

• 棋盘上的格子至多使用两种不同颜色；
• 棋盘上不存在边相邻且颜色相同的格子。

米哈伊尔考虑到，在太大的棋盘上对局会过于困难。因此，他可能会从自己的棋盘上裁出一个较小的棋盘，即保留前 $r$ 行和前 $c$ 列构成的矩形区域，并只将这一部分正确涂色。

对于每一对数 $r$ 和 $c$（$1 \le r \le n$，$1 \le c \le n$），请计算 $b_{r c}$ 的值——使得由前 $r$ 行和前 $c$ 列构成的矩形区域变为正确涂色，米哈伊尔最少需要重新涂色的格子数目。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 400$），表示棋盘的大小。

接下来的 $n$ 行描述棋盘：其中第 $i$ 行包含 $n$ 个整数 $a_{i 1}, \ldots, a_{i n}$（$1 \le a_{i j} \le 10^9$），表示棋盘第 $i$ 行各个格子的颜色。

输出格式

输出 $n$ 行，其中第 $i$ 行应包含 $n$ 个整数 $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

提示

子任务

翻译由 DeepSeek V4 Pro 完成