时空限制

1.5S/512M

题目描述

apiadu 拥有一片巨大的正方形农田，被划分成了 $n \times n$ 的方格。为了充分利用土地，他在每个方格里都种植了一种作物：苹果（用字符 a 表示）或者香蕉（用字符 b 表示）。

apiadu 定义上下左右相邻且种植同一种作物的方格，属于同一块“连通田地”。

为了保护作物，apiadu 计划给每一块连通田地都围上栅栏。栅栏需要安装在连通田地的边缘。具体来说，对于连通田地中的某一个方格，如果它的某个方向（上、下、左、右）是另一种作物的方格或者超出了农田的边界，那么该方向就需要安装一段长度为 $1$ 的栅栏。

一块连通田地的周长，就是包围这块田地所需的栅栏总长度。

对于农田中的每一个方格，请你计算出它所属的那块连通田地的周长是多少。

格式

输入格式

第一行包含一个整数 $n$，表示农田的边长。

接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串，仅由字符 'a' 和 'b' 组成，代表农田的作物分布情况。

输出格式

输出一个 $n \times n$ 的矩阵。

矩阵包含 $n$ 行，每行 $n$ 个整数，用空格隔开。

第 $i$ 行第 $j$ 列的整数，表示原始地图中位置 $(i, j)$ 的作物所属的连通田地的周长。

样例

样例输入 #1

4
aaab
abbb
aabb
bbbb

样例输出 #1

14 14 14 18
14 18 18 18
14 14 18 18
18 18 18 18

样例解释 #1

每个联通田地的长度如下图所示：

样例输入 #2

4
aaaa
bbba
abab
bbbb

样例输出 #2

12 12 12 12
20 20 20 12
4 20 4 20
20 20 20 20

数据规模

子任务编号	分数	$n \le$	子任务依赖
$1$	$40$	$100$	无
$2$	$60$	$2000$	$1$

对于 $100\%$ 的数据，$1 \le n \le 2000$，输入仅包含字符 a 和 b。