Туманная долина представлена в виде прямоугольной карты размера n на m. Некоторые клетки содержат спасательные маяки и обозначаются символом B. Скалы и завалы обозначаются символом #, а проходимые клетки — символом ..

Из любой проходимой клетки можно перейти в соседнюю по стороне проходимую клетку. Для каждой клетки карты требуется определить расстояние до ближайшего спасательного маяка.

Расстояние измеряется количеством переходов между соседними по стороне клетками. Для клетки, в которой уже стоит маяк, расстояние считается равным 0.

Если клетка является препятствием, для неё нужно вывести -1. Если клетка проходима, но из-за препятствий от неё невозможно добраться ни до одного маяка, для неё также нужно вывести -1.

Входные данные

В первой строке заданы два целых числа n и m.

Далее следуют n строк длины m, состоящие из символов ., # и B.

Гарантируется, что на карте есть хотя бы один спасательный маяк.

Выходные данные

Выведите n строк по m целых чисел.

Число в строке i и столбце j должно быть равно расстоянию от соответствующей клетки до ближайшего спасательного маяка, если клетка проходима. Если клетка является препятствием или недостижима ни от одного маяка, выведите -1.

Ограничения

• 1 <= n, m <= 1000
• n * m <= 200000

Примеры

Пример 1

Входные данные

1 1
B

Выходные данные

0

Пример 2

Входные данные

3 3
B#.
.#.
...

Выходные данные

0 -1 6
1 -1 5
2 3 4