5. Square in the Maze
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A maze of size $$$N \times M$$$ cells is given. In the upper left corner of the maze, there is a square with a side length of $$$P$$$ cells. In one step, the square can move one cell up, down, right, or left, provided it does not collide with occupied cells. You need to find the shortest possible path length for the square to reach the lower right corner.

Input

The first line contains three numbers $$$N$$$, $$$M$$$, $$$P$$$. Next, there are $$$N$$$ lines of $$$M$$$ characters representing the cells of the maze: '.' if the cell is free, 'X' if it is occupied. It is guaranteed that the upper left and lower right $$$P \times P$$$ squares do not contain occupied cells.

Output

Output the shortest possible path length, or $$$-1$$$ if such a path does not exist.

Examples
Input
5 5 2
...XX
....X
X...X
XX...
XX...
Output
6
Input
5 5 2
...XX
...XX
XX.XX
XX...
XX...
Output
-1
Note

Subtask 1 (up to 20 points): $$$1 \leq N,M \leq 10$$$, $$$P = 1$$$

Subtask 2 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$P = 1$$$

Subtask 3 (up to 20 points): $$$1 \leq N,M \leq 50$$$, $$$P = 2$$$

Subtask 4 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq \min(50,N,M)$$$

Subtask 5 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq \min(N,M)$$$