Задача F. Lode Runner возвращается ≡

Условие

Компания-разработчик компьютерных игр решила выпустить обновлённую версии классической аркадной игры Lode Runner.

Игра проходит в лабиринте, состоящем из горизонтальных платформ, соединённых лестницами. Лабиринт изображается в виде поля шириной W и высотой H клеток, каждая клетка которого содержит один из символов "." (ASCII 46) — свободное место, "X" (ASCII 88) — платформа и "#" (ASCII 35) — лестница.

По правилам игры, все платформы должны быть строго горизонтальными и не соприкасаться друг с другом (т.е. два символа "X" могут соседствовать только по горизонтали). Каждая лестница должна быть строго вертикальной и соединять две платформы (т.е. представлять собой вертикальную полосу из символов "#", над верхним и под нижним символом которой находятся символы "X"). Лестницы могут соприкасаться друг с другом, находясь на соседних вертикалях.

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

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

Поскольку времени на поиск нового дизайнеры уже не оставалось, было решено доработать имеющиеся уровни, заменив некоторые символы "." на "#" или наоборот. После этой доработки все лестницы должны соответствовать правилам игры. Кроме того, чтобы максимально сохранить первоначальный замысел дизайнера, количество замен следует минимизировать.

Требуется написать программу которая по данному описанию уровня игры строит уровень, соответствующий правилам и получающийся из данного минимально возможным количеством замен символов "." и "#" друг на друга.

Формат входного файла

Первая строка входного файла содержит целые числа W H. Следующие H строк содержат по W символов каждая — описание уровня.

Формат выходного файла

Выходной файл должен содержать H строк по W символов каждая — исправленное описание уровня. Если оптимальных решений несколько, выведите любое из них. Гарантируется, что хотя бы одно решение существует.

Ограничения

1 ≤ W, H ≤ 1000

Примеры тестов

6 4
.XX.X.
......
#.#...
XXXXX.

.XX.X.
..#.#.
..#.#.
XXXXX.