Карта Берляндии представляет собой прямоугольник размера n × m, состоящий из клеток размера 1 × 1. Каждая из клеток карты является либо сушей, либо водой. Со всех краёв Берляндия омывается океаном.
Озёрами называются такие связные по сторонам максимальные по включению области из клеток с водой, которые не имеют общих границ с океаном. Другими словами, озеро — это область клеток с водой, такая что из любой клетки можно добраться до любой другой, не покидая озера, двигаясь только между соседними по стороне клетками, никакая из клеток не расположена на границе прямоугольника и нельзя добавить ещё одну клетку с водой, так что по-прежнему можно будет добраться от любой клетки до любой другой.
Перед вами стоит задача засыпать землей минимальное количество клеток таким образом, чтобы в Берляндии стало ровно k озёр. Изначально на карте находятся не менее k озер.
Выходные данные
В первую строку выведите минимальное количество клеток, которые из воды нужно превратить в сушу.
В следующие n строк выведите m символов — карта после внесения в неё изменений. Формат должен строго соответствовать формату карты из входных данных (размеры карты выводить не нужно). Если решений несколько, выведите любое из них.
Гарантируется, что ответ всегда существует.
Примечание
В первом примере всего содержится два озера — первое состоит из клеток (2, 2) и (2, 3), а второе состоит из клетки (4, 3). Выгодно засыпать второе озеро, так как оно наименьшее по размеру. Обратите внимание, что участок воды в нижнем левом углу поля не является озером, так как этот участок граничит с океаном.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4 1
****
*..*
****
**.*
..**
|
1
****
*..*
****
****
..**
|
|
2
|
3 3 0
***
*.*
***
|
1
***
***
***
|