配点 : $200$ 点

問題文

縦 $R$ 行横 $C$ 列の盤面があります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

$(i,j)$ の現在の状態が文字 $B_{i,j}$ として与えられます。 . は空きマス、# は壁があるマスを表し、 1, 2,$\dots$, 9 はそれぞれ威力 $1,2,\dots,9$ の爆弾があるマスを表します。

次の瞬間に、全ての爆弾が同時に爆発します。 爆弾が爆発すると、爆弾があるマスからのマンハッタン距離がその爆弾の威力以下であるような全てのマス（その爆弾があるマス自体を含む）が空きマスに変わります。 ここで、$(r_1,c_1)$ から $(r_2,c_2)$ までのマンハッタン距離は $|r_1-r_2|+|c_1-c_2|$ です。

爆発後の盤面を出力してください。

制約

• $1\leq R,C \leq 20$
• $R,C$ は整数
• $B_{i,j}$ は ., #, 1, 2,$\dots$, 9 のいずれかである

入力

入力は以下の形式で標準入力から与えられる。

$R$ $C$

$B_{1,1}B_{1,2}\dots B_{1,C}$

$\vdots$

$B_{R,1}B_{R,2}\dots B_{R,C}$

出力

爆発後の盤面を $R$ 行で出力せよ。盤面の表し方は入力と同じ形式を用いること ($R$ と $C$ を出力する必要はない)。

4 4
.1.#
###.
.#2.
#.##

...#
#...
....
#...

• $(1,2)$ にある爆弾の爆発によって、上図の青いマスと紫のマスが空きマスに変わります。
• $(3,3)$ にある爆弾の爆発によって、上図の赤いマスと紫のマスが空きマスに変わります。

この例のように、爆弾が効果を及ぼす範囲に被りがあることもあります。

2 5
..#.#
###.#

..#.#
###.#

爆弾が $1$ つもないこともあります。

2 3
11#
###

...
..#

4 6
#.#3#.
###.#.
##.###
#1..#.

......
#.....
#....#
....#.