C. Восстание роботов пылесосов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В $$$2033$$$ году группа пылесосов под управлением ChatGPT захватила мир. Теперь люди выполняют их работу и чистят полы в их домах.

Дом представляет собой матрицу n на m, где символ «.» означает, что пол чист, а «*», что пол грязный.

К счастью захват мира привнес нечто новое — появилась волшебная квадратная тряпка со стороной длины $$$k$$$, с помощью неё за 1 секунду очистить любой полностью загрязненный квадрат размера $$$\textbf{строго} $$$ $$$k$$$ на $$$k$$$.

Роботы-пылесосы не любят ждать, поэтому необходимо выполнить работу за кратчайшее время.

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

В первой строке записаны три целых числа $$$n,m,k$$$ $$$(1 \le n,m,k \le 10^5, 1 \le n \cdot m \le 10^5)$$$ — размеры дома и тряпки

Далее следуют $$$n$$$ строк по $$$m$$$ символов — загрязненность клеток дома

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

Выведите одно целое число — ответ на задачу, если очистить дом полностью невозможно выведите -1

Система оценки

Всего в задаче $$$25$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 4 балла.

Примеры
Входные данные
4 4 2
**..
**..
..**
..**
Выходные данные
2
Входные данные
4 4 2
**..
*...
..**
..**
Выходные данные
-1