题目描述

有一个 $R$ 行 $C$ 列的盘面，点 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。上面有三种状态，. 代表空地，# 代表一堵墙，1, 2, 3 ... 9 代表炸弹。上面的 1 ~ 9 代表炸弹的威力值。

下面，所有的炸弹同时爆炸，所有曼哈顿距离小于等于每个点上的威力值的墙将变成空地。

注意：如果该点在爆炸范围内，且该点是炸弹，则不会变成空地。爆炸后，该炸弹本身会变成空地。

你需要输出爆炸后的盘面。

输入格式

第一行，两个数字，代表 $R$ 和 $C$。

接下来 $R$ 行，代表盘面的每一行。

输出格式

$R$ 行，爆炸后的盘面。

数据规模与约定

• $1 \le R, C \le 20$
• $R, C$ 均为整数
• 每个地方只能是 ., #, 1, 2, 3 ... 9 的字符

样例 1

输入

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

输出

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

样例 2

输入

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

输出

..#.#
###.#

样例 3

输入

2 3
11#
###

输出

...
..#

样例 4

输入

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

输出

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