D. Озёра в Берляндии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карта Берляндии представляет собой прямоугольник размера n × m, состоящий из клеток размера 1 × 1. Каждая из клеток карты является либо сушей, либо водой. Со всех краёв Берляндия омывается океаном.

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

Перед вами стоит задача засыпать землей минимальное количество клеток таким образом, чтобы в Берляндии стало ровно k озёр. Изначально на карте находятся не менее k озер.

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

В первой строке входных данных записаны три целых положительных числа n, m и k (1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50) — размеры карты и количество озёр, которые должны остаться на карте.

В следующих n строках следует по m символов — описание карты. Каждый из символов — либо «.» (означает, что соответствующая клетка это участок с водой), либо «*» (означает, что соответствующая клетка — это участок суши).

Гарантируется, что на данной карте не менее k озер.

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

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

В следующие n строк выведите m символов — карта после внесения в неё изменений. Формат должен строго соответствовать формату карты из входных данных (размеры карты выводить не нужно). Если решений несколько, выведите любое из них.

Гарантируется, что ответ всегда существует.

Примеры
Входные данные
5 4 1
****
*..*
****
**.*
..**
Выходные данные
1
****
*..*
****
****
..**
Входные данные
3 3 0
***
*.*
***
Выходные данные
1
***
***
***
Примечание

В первом примере всего содержится два озера — первое состоит из клеток (2, 2) и (2, 3), а второе состоит из клетки (4, 3). Выгодно засыпать второе озеро, так как оно наименьшее по размеру. Обратите внимание, что участок воды в нижнем левом углу поля не является озером, так как этот участок граничит с океаном.