Наконец настал тот день, когда Артур накопил достаточную сумму денег и решил купить квартиру. Ему предложили отличный вариант — квартиру в самом центре города по отличной цене.
План предложенной Артуру квартиры представляет собой прямоугольник размера n × m, разделенный на квадраты размера 1 × 1. В каждом из таких квадратов находится либо стена (такой квадрат обозначен на плане символом "*"), либо свободное от стены место (такой квадрат обозначен на плане символом ".").
Комнаты в квартире представляют собой максимальные по размеру связные области из клеток, свободных от стен. Две клетки считаются соседними, если они имеют общую сторону.
Давней мечтой Артура была квартира, в которой все комнаты представляют собой прямоугольники. Он просит вас посчитать минимальное количество стен, которое нужно удалить для осуществления его мечты. После удаления из клетки стены в ней образуется свободное место. В процессе удаления стен несколько комнат могут объединиться в одну.
Выходные данные
Выведите n строк по m символов — как будет выглядеть план квартиры Артура, после удаления минимального количества стен для того, чтобы каждая комната (максимальная по размеру связная область из свободных от стен мест), представляла собой прямоугольник.
Если возможных ответов несколько, разрешается вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
.*.*.
*****
.*.*.
*****
.*.*.
|
.*.*.
*****
.*.*.
*****
.*.*.
|
|
2
|
6 7
***.*.*
..*.*.*
*.*.*.*
*.*.*.*
..*...*
*******
|
***...*
..*...*
..*...*
..*...*
..*...*
*******
|
|
3
|
4 5
.....
.....
..***
..*..
|
.....
.....
.....
.....
|