给定一个由 n × m 个单元格组成的矩形区域。每个单元格要么是空的,要么是无法通过的(包含障碍物)。空单元格用“.”标记,不可通过的单元格用“*”标记。如果两个空单元格共用一条边,我们称它们为相邻单元格。
我们将连接组件称为任何不可扩展的单元集,其中任何两个单元都通过相邻单元的路径连接。这是连接组件的典型众所周知的定义。
对于每个不可通过的单元格 (x, y),想象它是一个空单元格(所有其他单元格保持不变),并找到包含 (x, y) 的连通分量的大小(单元格数量)。您应该独立地为每个不可通过的单元格执行此操作。
答案应打印为 n 行 m 列的矩阵。第 i 行的第 j 个符号应该是“.”。如果单元格在开始时为空。否则,第 i 行的第 j 个符号应包含唯一的数字 ---- 答案模 10。打印的矩阵应不带任何空格。
为了使输出更快,建议将输出构建为长度为 m 的 n 个字符串数组,并将其打印为行序列。这比逐个字符写要快得多。
由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在C++中更喜欢使用scanf/printf而不是cin/cout,在Java中更喜欢使用BufferedReader/PrintWriter而不是Scanner/System.out。
输入
第一行包含两个整数 n、m (1 ≤ n, m ≤ 1000) — 字段中的行数和列数。
接下来的 n 行每一行包含 m 个符号:“.”对于空单元格,“*”对于无法通过的单元格。
输出
如上所述将答案打印为矩阵。请参阅示例以精确输出的格式。
示例
输入 #1
3 3 *.* .*. *.*
输出 #1
3.3 .5. 3.3
输入 #2
4 5 **..* ..*** .*.*. *.*.*
输出 #2
46..3 ..732 .6.4. 5.4.3
注意
在第一个示例中,如果我们假设中心单元格是空的,那么它将包含在尺寸为 5(十字)的组件中。如果任何角单元为空,则它将包含在尺寸为 3(角)的组件中。