Защитный узор
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Входная дверь Беверли представляет собой клетчатый прямоугольник размера $$$n \times m$$$. Каждая клетка прямоугольника покрашена в белый или черный цвет. Беверли считает, что узор на двери будет отпугивать Пенивайза, если:

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

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

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

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

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

Примеры

Входные данные
3 3
###
#.#
###
Выходные данные
###
#.#
##.
Входные данные
4 3
##.
.##
###
##.
Выходные данные
##.
.##
#.#
###
Входные данные
2 3
...
...
Выходные данные
...
#..

Примечание

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

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

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