Задача K. Минимальный лабиринт ≡

Условие

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

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

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

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

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

Первая строка входного файла содержит два целых числа — N M.

Далее идут N строк по M символов, описывающие лабиринт:

• # (ASCII 35) — обозначает блок
• . (ASCII 46) — обозначает пустое место

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

Выходной файл должен содержать N строк по M символов — описание нового оптимизированного лабиринта в формате, идентичном входному.

Ограничения

1 ≤ N, M ≤ 100

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

3 7
......#
.#..#.#
....#..

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

3 8
##.#..##
##.#.###
...#.##.

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