#3088. Magic Formation

Magic Formation

Background

SABRINA\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A} 被困在魔法阵里了!

Description

SABRINA\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A} 手上有一张地图,这张地图由 W_ 组成,W 表示荆棘,_ 表示空地。

SABRINA\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A} 必须准确的说出每个荆棘周围的连通块中的空地的数量和,才能逃出魔法阵!答案对 1010 取模。

注意属于同一个连通块的只计算一次,当前点需计算在内。

Format

Input

第一行,包含两个整数 n,mn,m ( 1<=n,m<=1000 1<=n,m<=1000 )

接下来 nnmm 列,输入由 W_ 组成的地图。

Output

将答案输出为如上所述的矩阵,参考示例以准确输出的格式。

样例 #1

样例输入 #1

4 5
WW__W
__WWW
_W_W_
W_W_W

样例输出 #1

46__3
__732
_6_4_
5_4_3