问题描述

我们有一个 $R$ 行 $C$ 列的棋盘，水平方向从上到下编号为 $i$，垂直方向从左到右编号为 $j$。

给定字符 $B_{i,j}$ 表示 $(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$）。

示例输入 1

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

示例输出 1

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

• 在上面的图示中，$(1,2)$ 处的炸弹爆炸，将把蓝色和紫色方块变为空方块。
• 在上面的图示中，$(3,3)$ 处的炸弹爆炸，将把红色和紫色方块变为空方块。

正如这个示例所示，炸弹的爆炸范围可能会重叠。

示例输入 2

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

示例输出 2

..#.#
###.#

可能没有炸弹。

示例输入 3

2 3
11#
###

示例输出 3

...
..#

示例输入 4

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

示例输出 4

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