1987 - bomb
Description

在R x C的网格中,每个格子上有三种状态,. 表示空地,# 表示障碍物,123,,9 表示炸弹,网格上标注的数字表示炸弹的威力。

一个位于(x,y)的炸弹引爆后,假设其威力值为c,所有格子(a,b)满足|a-x|+|b-y|<=c的位置都会被炸为空地。

现在同时引爆所有炸弹,请你输出所有炸弹爆炸后网格的状况。


Input

第一行包含2个正整数,表示R和C。

接下来R行,每行C个字符,表示网格状况。


Output

输出共R行,每行C个字符,表示网格状况。


Examples

Input

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

Output

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

Input

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

Output

......
#.....
#....#
....#.
Hint

样例解释1

网格 (1,2)上的炸弹威力为1,会波及到的位置为(1,1),(1,2),(1,3),(2,2)。

网格 (3,3)上的炸弹威力为 ,会波及到的位置为 (2,2)(2,3)(2,4)(3,2)(3,3)(3,4)(4,2)(4,3)(4,4)(1,3)(3,1)。

数据范围:

  • 对于20% 的数据,原网格上没有炸弹。

  • 对于另外20%的数据,1 \leq R,C \leq 100

  • 对于 100% 的数据,1 \leq R,C \leq 1000


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 40
通过次数 15