Problem Description

Given a $R \times C$ map where . represents walkable cells and # represents non-walkable cells. An operation can transform all cells within an $N \times N$ square to . Given a starting point and an endpoint, find the minimum number of operations required to make the starting point and the endpoint connected (movement is restricted to up, down, left, and right).

Constraints: $R \times C \leq 6 \times 10^6$, $N \leq R \leq C$.

Problem Description

President K loves solving mazes. He found cells from which he may create a maze. The cells are arranged in a rectangular grid with $R$ rows and $C$ columns. Each cell is either white or black. The cell in the $i$-th row from the top and the $j$-th column from the left is called Cell $(i, j)$.

President K can only pass through white cells and cannot pass through black cells. He will solve the maze by choosing a starting cell $(S_r, S_c)$ and a goal cell $(G_r, G_c)$ among the white cells. He can move from one cell to another adjacent white cell in one of the four directions (top, bottom, left, or right) to find a path from the starting cell to the goal cell.

President K has already fixed the starting and goal cells. However, he noticed that in some configurations of the cell colors, there might not be a path from the starting cell to the goal cell consisting only of white cells. He has a stamp of size $N \times N$. He will perform the following Operation several times to ensure there is a path from the starting cell to the goal cell consisting only of white cells.

Operation. He chooses a square region of $N \times N$ cells and paints all cells in this region white. Specifically, he chooses integers $a, b$ satisfying $1 \leq a \leq R - N + 1$ and $1 \leq b \leq C - N + 1$, and for every pair $(i, j)$ of integers satisfying $a \leq i \leq a + N - 1$ and $b \leq j \leq b + N - 1$, he paints Cell $(i, j)$ white.

Since his hands become dirty if he uses the stamp, he wants to minimize the number of operations. Given information about the colors of the cells, the size of the stamp, and the locations of the starting and goal cells, write a program to calculate the minimum number of operations he has to perform so that there will be a path from the starting cell to the goal cell consisting only of white cells.

Input Format

Read the following data from the standard input:

$R$ $C$ $N$
$S_r$ $S_c$
$G_r$ $G_c$
$A_1$
$A_2$
$.$
$.$
$.$
$A_R$

$A_i (1 \leq i \leq R)$ is a string of length $C$ consisting of . or #. The $j$-th character ($1 \leq j \leq C$) of $A_i$ represents the color of Cell $(i, j)$. Its color is white if the character is ., and its color is black if the character is #.

Output Format

Write one line to the standard output. The output should contain the minimum number of operations President K has to perform so that there will be a path from the starting cell to the goal cell consisting only of white cells.

Sample Input and Output

Sample Input #1

2 4 2
1 1
2 4
.###
###.

Sample Output #1

1

Sample Input #2

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

Sample Output #2

4

Sample Input #3

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

Sample Output #3

1

Sample Input #4

1 15 1
1 15
1 1
...............

Sample Output #4

0

Notes/Hints

Sample Explanation #1

If he chooses $(a, b) = (1, 2)$ and performs an operation, Cells $(1, 2), (1, 3), (2, 2), (2, 3)$ become white. Then there will be a path from the starting cell to the goal cell consisting only of white cells. For example, the path $(1, 1) → (1, 2) → (1, 3) → (2, 3) → (2, 4)$ satisfies the condition.

If he does not perform an operation, there is no path from the starting cell to the goal cell consisting only of white cells. Therefore, output $1$.

This sample satisfies the constraints of subtasks $2, 3, 4, 5, 6, 7, 8$.

Sample Explanation #2

This sample satisfies the constraints of all subtasks.

Sample Explanation #3

This sample satisfies the constraints of subtasks $2, 3, 4, 5, 6, 7, 8$.

Sample Explanation #4

Even if he does not perform an operation, there might be a path from the starting cell to the goal cell consisting only of white cells.

This sample satisfies the constraints of all subtasks.

Data Range

For all test data, the following constraints apply:
- $1 \leq N \leq R \leq C$
- $R \times C \leq 6 \times 10^6$
- $1 \leq S_r \leq R$
- $1 \leq S_c \leq C$
- $1 \leq G_r \leq R$
- $1 \leq G_c \leq C$
- $(S_r, S_c) \neq (G_r, G_c)$

The strings $A_i (1 \leq i \leq R)$ are of length $C$ and consist only of . or #. The cells $(S_r, S_c)$ and $(G_r, G_c)$ are guaranteed to be white.

The values $R, C, N, S_r, S_c, G_r, G_c$ are all integers.

见题面 Input 部分

见题面 Output 部分