У нас є дошка з \(R\) рядками, розташованими горизонтально, і \(C\) стовпцями, розташованими вертикально. Нехай \((i,j)\) позначає квадрат у \(i\)-му рядку зверху та \(j\)-му стовпчику зліва.

Вам надано символи \(B_{i,j}\), що представляють поточний стан \((i,j)\). . позначає порожній квадрат; # позначає квадрат зі стіною; 1, 2, …, 9 представляють квадрат із бомбою потужністю 1,2,…,9 відповідно.

У наступний момент всі бомби вибухнуть одночасно. Коли бомба вибухне, кожен квадрат, відстань якого до квадрата з бомбою не перевищує потужності бомби, перетвориться на порожній квадрат. Тут манхеттенська відстань від \((r_1 ​ ,c_1 ​ )\) до \((r_2 ​ ,c_2 ​ )\) дорівнює \(∣r_1 ​ −r_2 ​ ∣+ ∣c_1 ​ −c_2 ​ ∣\).

Виведіть дошку після вибухів.

Обмеження

• \(1≤R,C≤20\)
• \(R\) і \(C\) є цілими числами.
• Кожен \(B_{i,j}\) ​ є одним із ., #, 1, 2, …, 9.

Формат вхідних даних

Перший рядок містить цілі числа \(R,C\).

Наступні  \(R\) рядків містять \(C\) символів \(B_{i,j}\).

Формат вихідних даних

У вихідний потік виведіть R рядків, що представляють дошку після вибухів.

Використовуйте формат, використаний у вхідних даних (не виводіть \(R\) або \(C\)).

Приклад вхідних даних

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

Приклад вихідних даних

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

• Вибух бомби в (1,2) перетворить сині та фіолетові квадрати на малюнку вище на порожні квадрати.
• Вибух бомби в (3,3) перетворить червоні та фіолетові квадрати на малюнку вище на порожні квадрати.

Як видно з цього прикладу, радіуси вибуху бомб можуть збігатися.

Приклад вхідних даних

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

Приклад вихідних даних

..#.#
###.#

Бомби може не бути.

Приклад вхідних даних

2 3
11#
###

Приклад вихідних даних

...
..#

Приклад вхідних даних

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

Приклад вихідних даних

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