B. И снова тетрис
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В редких перерывах между поисками теории всего физик Воль играет в расслабляющую игру — модифицированный им тетрис.

Компьютер выдает Волю прямоугольное игровое поле n × m, на котором некоторые клетки пустые, остальные же заполнены. Игровая панель рядом с полем содержит изображения всевозможных связных фигурок, содержащих от двух до пяти клеток. Здесь мы рассматриваем только связные по стороне фигурки. Фигурки можно копировать с игровой панели на поле, заполняя ими пустые клетки. Разумеется, каждую фигурку можно использовать сколько угодно раз.

Задача Воля — заполнить все поле так, чтобы на нем не осталось пустых клеток.

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

На рисунке черные клетки — изначально заполненные клетки поля, а одноцветные связные области — фигурки.

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

Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 1000), n и m — высота и ширина поля соответственно. Следующие n строк содержат по m символов каждая. Они естественным образом описывают поле: j-ый символ i-ой строки равен «#», если соответствующая клетка поля занята, и «.», если соответствующая клетка поля свободна и должна быть покрыта некоторой фигуркой.

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

Если поле заполнить невозможно, выведите единственной число «-1» (без кавычек). Иначе выведите любое заполнение поля фигурками в формате, совпадающем с входным, где все «.» (пустые клетки) заменены описанием фигурок следующим образом (см. примеры): каждая фигурка должна быть выведена конкретной цифрой, при этом касающимся по стороне фигуркам должны соответствовать разные цифры.

Примеры
Входные данные
2 3
...
#.#
Выходные данные
000
#0#
Входные данные
3 3
.#.
...
..#
Выходные данные
5#1
511
55#
Входные данные
3 3
...
.##
.#.
Выходные данные
-1
Входные данные
1 2
##
Выходные данные
##
Примечание

В третьем примере невозможно заполнить пустую клетку, у которой нет пустых соседей.

В четвертом примере ничего заполнять не нужно, поэтому надо вывести исходное поле.