题目描述

我们有一个 $R$ 行 $C$ 列的网格。记从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子为 $(i, j)$。

网格中格子的状态由字符 $B_{i,j}$ 表示：. 表示空地；# 表示有墙；1 到 9 表示放置了对应威力值（$1$ 到 $9$）的炸弹。

下一时刻，所有炸弹将同时爆炸。当炸弹在格子 $(r_1, c_1)$ 爆炸时，所有满足与该格子的曼哈顿距离不超过炸弹威力值的格子 $(r_2, c_2)$ 都将变成空地。两点之间的曼哈顿距离定义为 $|r_1 - r_2| + |c_1 - c_2|$。请输出爆炸后的网格状态。

输入格式

第一行包含两个正整数 $R$ 和 $C$ —— 分别表示网格的行数和列数。

接下来 $R$ 行，每行包含一个长度为 $C$ 的字符串，表示网格的状态。

输出格式

输出 $R$ 行，每行包含一个长度为 $C$ 的字符串，表示爆炸后的网格状态。

样例输入 1

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

样例输出 1

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

样例输入 2

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

样例输出 2

..#.#
###.#

样例输入 3

2 3
11#
###

样例输出 3

...
..#

样例输入 4

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

样例输出 4

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

说明

样例解释

• 在第一个样例中：

  • 位于 $(1, 2)$ 的炸弹爆炸，将其曼哈顿距离范围内的格子清空。
  • 位于 $(3, 3)$ 的炸弹爆炸，将其曼哈顿距离范围内的格子清空。
  • 炸弹的爆炸范围可能会重叠。

• 在第二个样例中，由于没有任何炸弹，网格状态不发生改变。

数据范围

• 对于所有测试点，保证 $1 \le R, C \le 20$。
• 保证 $B_{i,j}$ 为 ., # 或数字 1 到 9。
• 保证所有的输入值均为整数。