D. Артур и стены
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наконец настал тот день, когда Артур накопил достаточную сумму денег и решил купить квартиру. Ему предложили отличный вариант — квартиру в самом центре города по отличной цене.

План предложенной Артуру квартиры представляет собой прямоугольник размера n × m, разделенный на квадраты размера 1 × 1. В каждом из таких квадратов находится либо стена (такой квадрат обозначен на плане символом "*"), либо свободное от стены место (такой квадрат обозначен на плане символом ".").

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

Давней мечтой Артура была квартира, в которой все комнаты представляют собой прямоугольники. Он просит вас посчитать минимальное количество стен, которое нужно удалить для осуществления его мечты. После удаления из клетки стены в ней образуется свободное место. В процессе удаления стен несколько комнат могут объединиться в одну.

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

В первой строке входных данных следуют два целых числа n, m (1 ≤ n, m ≤ 2000) — размеры плана квартиры Артура.

В следующих n строках задано по m символов — описание плана квартиры.

Если клетка плана обозначена символом "*", значит в ней находится стена.

Если клетка карты обозначена символом ".", значит в этом месте квартиры свободное от стены место, и эта клетка относится к какой-то из комнат.

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

Выведите n строк по m символов — как будет выглядеть план квартиры Артура, после удаления минимального количества стен для того, чтобы каждая комната (максимальная по размеру связная область из свободных от стен мест), представляла собой прямоугольник.

Если возможных ответов несколько, разрешается вывести любой из них.

Примеры
Входные данные
5 5
.*.*.
*****
.*.*.
*****
.*.*.
Выходные данные
.*.*.
*****
.*.*.
*****
.*.*.
Входные данные
6 7
***.*.*
..*.*.*
*.*.*.*
*.*.*.*
..*...*
*******
Выходные данные
***...*
..*...*
..*...*
..*...*
..*...*
*******
Входные данные
4 5
.....
.....
..***
..*..
Выходные данные
.....
.....
.....
.....