20220240 - 连通

Time Limit

200 毫秒

Memory Limit

128 MB

通过次数

6

提交次数

20

一个hw列的地图,*表示墙,.表示空地,输出每个块墙连通的空地数量。

连通:上下左右四个方向相邻的视为连通。

Input

第一行,h,w

剩下行的是地图。

对于100%的数据:

1 \le h,w \le 10^3

Output

每块墙所连通的空地的大小对10取余的结果。

Examples

Input

3 3
*.*
.*.
*.*

Output

2.2
.4.
2.2

Input

4 5
**..*
..***
.*.*.
*.*.*

Output

35..2
..621
.5.3.
4.3.2