Maze

President K loves solving mazes. He found a grid of cells from which he may create a maze. The grid has $R$ horizontal rows and $C$ vertical columns. Each cell is colored either white or black. The cell in the $i$-th row ($1 \le i \le R$) from the top and the $j$-th column ($1 \le j \le C$) from the left is called Cell $(i, j)$.

President K solves the maze under the condition that he can pass white cells but cannot pass black cells. He solves it in the following way.

1. He chooses, among the white cells, the starting cell $(S_r, S_c)$ and the goal cell $(G_r, G_c)$.
2. He can move from the current cell to an adjacent white cell in one of the four directions (up, down, left, or right). He repeats this until he finds a path from the starting cell to the goal cell.

The starting cell and the goal cell are already fixed. Depending on the colors, there may be no path from the starting cell to the goal cell made of white cells only. President K has a stamp of size $N \times N$. He performs the following operation several times so that a path made of white cells only exists from the starting cell to the goal cell.

Operation: He chooses a square region of $N \times N$ cells and paints every cell in it white. Concretely, he chooses integers $a$ and $b$ with $1 \le a \le R - N + 1$ and $1 \le b \le C - N + 1$, and paints white every Cell $(i, j)$ with $a \le i \le a + N - 1$ and $b \le j \le b + N - 1$.

Using the stamp makes his hands dirty, so he wants as few operations as possible. Given the colors of the cells, the stamp size, and the positions of the starting and goal cells, write a program that computes the minimum number of operations needed to create a path of white cells from the starting cell to the goal cell.

The first line contains $R$, $C$, and $N$.

The second line contains $S_r$ and $S_c$.

The third line contains $G_r$ and $G_c$.

The next $R$ lines each contain a string $A_i$ of length $C$ made of . and #. The $j$-th character of $A_i$ is . if Cell $(i, j)$ is white and # if it is black.

Print one line containing the minimum number of operations President K has to perform so that a path of white cells from the starting cell to the goal cell exists.

• $1 \le N \le R \le C$.
• $R \times C \le 6\,000\,000$.
• $1 \le S_r \le R$, $1 \le S_c \le C$, $1 \le G_r \le R$, $1 \le G_c \le C$.
• $(S_r, S_c) \ne (G_r, G_c)$.
• $A_i$ ($1 \le i \le R$) is a string of length $C$ consisting of . or #.
• Cell $(S_r, S_c)$ and Cell $(G_r, G_c)$ are white.
• $R$, $C$, $N$, $S_r$, $S_c$, $G_r$, $G_c$ are integers.