题目内容

在一片由水域和岩石构成的矩形地图上，有一块 $n \times m$ 的网格区域。每个格子要么是水域，要么是岩石，分别用字符 W 和 R 表示。

我们定义岩石的连通块为：通过上下左右相邻连通的岩石格子组成的集合。一个连通块最少包含一个岩石格子，不同连通块之间被水域隔开。

现在，想要考察每个格子的重要性。对于网格中的每个格子 $(i,j)$，进行一次假设性的操作：将该格子临时变为水域（若它原本就是水域则不发生变化）。在这一假设下，地图上岩石的分布可能改变，请计算此时整张地图上岩石连通块的数量。

你需要对每一个格子都计算这样一个数量，并输出完整的 $n \times m$ 答案矩阵。

数据约束：行数 $n$ 和列数 $m$ 满足 $1 \le n, m \le 40$，且输入中仅包含字符 W 和 R。

输入描述

第一行包含两个整数 $n$ 和 $m$，用一个空格隔开。 接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 W 或 R；同一行的字符之间可以没有空格，也可以用空格分隔。

输出描述

输出 $n$ 行，每行包含 $m$ 个整数，整数之间用一个空格隔开。其中第 $i$ 行第 $j$ 个整数表示将格子 $(i,j)$ 临时变为水域后，整张地图上岩石连通块的数量。

样例1

输入

1 1
R

输出

0

说明

将唯一的岩石变为水域后，地图上没有岩石，因此岩石连通块数量为 0。

样例2

输入

3 1
R
R
R

输出

1
2
1

说明

三个岩石竖直排列。对于第一个岩石（顶部），将其变为水域后，剩下两个岩石仍然上下相邻，形成 1 个连通块；对于中间的岩石，变为水域后，上下两个岩石被隔开，形成 2 个连通块；对于底部岩石，同理剩下两个岩石还是相邻，连通块数量为 1。

样例3

输入

2 2
W R
R R

输出

1 1
1 2

说明

原图中，三个岩石通过相邻关系连成 1 个连通块。对于位置 $(1,1)$，它原本就是水域，不变，连通块仍为 1。对于 $(1,2)$，变为水域后，剩下的两个岩石左右相邻，连通块为 1。对于 $(2,1)$，变为水域后，剩下的两个岩石上下相邻，连通块为 1。对于 $(2,2)$，变为水域后，剩下的两个岩石仅斜对角相邻，没有公共边，被水域隔开，因此形成 2 个连通块。