5. Квадрат в лабиринте
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан лабиринт размером $$$N \times M$$$ клеток. В верхнем левом углу лабиринта находится квадрат со стороной $$$P$$$ клеток. За один шаг квадрат может перемещаться на одну клетку вверх, вниз, вправо или влево, если при этом он не столкнется с занятыми клетками. Необходимо найти наименьшую возможную длину пути, по которой квадрат может добраться до нижнего правого угла.

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

В первой строке вводятся три числа $$$N$$$, $$$M$$$, $$$P$$$. Далее идет $$$N$$$ строк по $$$M$$$ символов, обозначающих клетки лабиринта: '.', если клетка свободна, 'X', если занята. Гарантируется, что верхний левый и нижний правый квадраты $$$P \times P$$$ не содержат занятых клеток.

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

Выведите наименьшую возможную длину пути, или $$$-1$$$, если такого пути не существует.

Примеры
Входные данные
5 5 2
...XX
....X
X...X
XX...
XX...
Выходные данные
6
Входные данные
5 5 2
...XX
...XX
XX.XX
XX...
XX...
Выходные данные
-1
Примечание

Подзадача 1 (до 20 баллов): $$$1 \leq N,M \leq 10$$$, $$$P = 1$$$

Подзадача 2 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$P = 1$$$

Подзадача 3 (до 20 баллов): $$$1 \leq N,M \leq 50$$$, $$$P = 2$$$

Подзадача 4 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq min(50,N,M)$$$

Подзадача 5 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq min(N,M)$$$