炸弹

题目描述

我们有一个 $R$ 行 $C$ 列的棋盘。设 $(i,j)$ 表示从上往下第 $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|$。

请输出爆炸后的棋盘。

输入格式

输入按以下格式从标准输入给出：

$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
..#.#
###.#

..#.#
###.#

可能没有炸弹。

2 3
11#
###

...
..#

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

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

数据范围

• $1\leq R,C \leq 20$
• $R$ 和 $C$ 是整数。
• 每个 $B_{i,j}$ 是 .、#、1, 2, $\dots$, 9 中的一个。