C. Лабиринт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано прямоугольное клетчатое поле размером n × m. Каждая клетка либо является пустой и обозначена символом ".", либо является непроходимой (содержит препятствие) и обозначена символом "*". Пустые клетки будем называть соседними, если они имеют общую сторону.

Компонентой связности будем называть наибольшее по включению множество свободных клеток причём между любой парой клеток в компоненте существует путь из свободных клеток такой, что любые две подряд идущие клетки в пути являются соседними. Это стандартное определение компоненты связности.

Вам нужно для каждой непроходимой клетки определить размер компоненты связности (количество клеток в компоненте), включающей эту клетку, если бы клетка была свободной. Заметим, что при определении этой величины свободной считается только та непроходимая клетка, для которой считается величина, остальные непроходимые клетки остаются таковыми.

Ответ нужно вывести в виде матрицы из n строк и m столбцов. В i-й строке j-м столбце должен находиться символ ".", если клетка изначально была свободной и ответ в противном случае. Для удобства ответы нужно посчитать по модулю 10 (то есть найти остаток при делении на число 10). Матрицу нужно вывести без пробелов. Для ускорения вывода рекомендуется записать каждую строку ответа в одну строку и вывести её.

Рекомендуется для ввода и вывода данных использовать функции scanf, printf в языке C++, поскольку они работают значительно быстрее потоков cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.

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

В первой строке находится пара целых чисел n, m (1 ≤ n, m ≤ 1000) — количество строк и столбцов.

В каждой из следующих n строк находится по m символов: "." обозначает пустую клетку, "*" обозначает непроходимую клетку.

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

Выведите ответ в виде матрицы как описано в условии задачи. Для уточнения формата вывода смотрите примеры.

Примеры
Входные данные
3 3
*.*
.*.
*.*
Выходные данные
3.3
.5.
3.3
Входные данные
4 5
**..*
..***
.*.*.
*.*.*
Выходные данные
46..3
..732
.6.4.
5.4.3
Примечание

В первом примере, если бы центральная клетка была свободной, то она вошла бы в компоненту связности из пяти клеток (крестик). Угловые клетки, если бы были свободными образовывали бы компоненты из трёх клеток (уголки).