题目描述

米哈伊尔决定学习玩“广义国际象棋”，于是准备了一块大小为 $n\times n$ 的棋盘。位于第 $i$ 行第 $j$ 列的格子被涂成颜色 $a_{i,j}$。

米哈伊尔是初学者，可能把棋盘涂错了。因此，有些格子可能需要重新涂成其他颜色。若一块棋盘满足以下两个条件，则称它被正确染色：

1. 棋盘上的格子使用的颜色不超过两种；
2. 任意两个有公共边的相邻格子颜色不同。

米哈伊尔觉得大棋盘太难玩了。因此，他可能会从原棋盘中锯下一块较小的棋盘，只保留前 $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},a_{i,2},\ldots,a_{i,n}\quad (1\le a_{i,j}\le 10^9),$$

表示第 $i$ 行各个格子的颜色。

输出格式

输出 $n$ 行，其中第 $i$ 行应包含 $n$ 个整数

$$b_{i,1},b_{i,2},\ldots,b_{i,n}。$$

样例 1

2
7 7
7 7

0 1
1 2

样例 2

3
1 1 2
2 4 4
3 1 2

0 1 1
0 2 4
1 3 5

子任务与评分

子任务	分值	附加限制	必要子任务
1	11	$n\le 50$	样例
2	22	$n\le 200$	样例，1
3	8	$a_{i,j}\le 2$	-
4	17	$a_{i,j}\le 10$	样例，3
5	15	$a_{i,j}\le 100$	样例，3-4
6	7	$a_{i,j}\le 10^4$	样例，3-5
7	20	无	样例，1-6

难度评估