Алёна прочитала в старой книге, которую нашла в библиотеке, что некоторые узоры могут отпугивать баги. Теперь она хочет нарисовать специальный узор на крышке своего макбука, чтобы успешно выпустить релиз.

Крышка макбука представляет собой клетчатый прямоугольник размера n x m. Каждая клетка прямоугольника покрашена в белый или черный цвет. Алёна считает, что узор на крышке будет отпугивать баги, если:

• На крышке будет хотя бы одна черная клетка
• Если соединить ребрами соседние по стороне черные клетки, в этом графе:
  • Будет одна компонента связности
  • Не будет существовать простого цикла

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

Формат входных данных

В первой строке даны два целых числа n и m - высота и ширина крышки (1 ⩽ n ⩽ 100, 1 ⩽ m ⩽ 10). В следующих n строках дано по m символов . и # - описание исходного узора на крышке. Символ . соответствует белому цвету, а # - черному.

Формат выходных данных

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

Пример

Примечание

В первом тесте Алёне потребуется перекрасить минимум одну клетку.

Во втором тесте Алёне потребуется перекрасить минимум две клетки.

В третьем тесте Алёне потребуется перекрасить минимум одну клетку.