K 先生喜欢解迷宫。他发现了一些可以用来制作迷宫的格子。这些格子构成了一个有 $R$ 行 $C$ 列的矩形网格。每个格子要么是白色的，要么是黑色的。从上往下数第 $i$ 行（$1 \le i \le R$），从左往右数第 $j$ 列（$1 \le j \le C$）的格子被称为格子 $(i, j)$。

K 先生将在只能通过白色格子，不能通过黑色格子的条件下解迷宫。更准确地说，他将按以下方式解迷宫：

1. 在白色格子中，他会选择格子 $(S_r, S_c)$ 作为迷宫的起点，格子 $(G_r, G_c)$ 作为迷宫的终点。
2. 可以从当前格子移动到与其在四个方向（上、下、左、右）之一相邻的白色格子。通过重复此操作，他将找到一条从起点到终点的路径。

K 先生已经确定了起点和终点。然而，他注意到在某些格子颜色的分布情况下，可能不存在一条仅由白色格子组成的从起点到终点的路径。他有一个大小为 $N \times N$ 的印章。他将执行若干次以下操作，使得存在一条仅由白色格子组成的从起点到终点的路径。

操作：他选择一个 $N \times N$ 的正方形区域，并将该区域内的格子涂成白色。更准确地说，他选择满足 $1 \le a \le R - N + 1$ 和 $1 \le b \le C - N + 1$ 的整数 $a, b$，对于满足 $a \le i \le a + N - 1$ 和 $b \le j \le b + N - 1$ 的每一对整数 $(i, j)$，他将格子 $(i, j)$ 涂成白色。

由于使用印章会弄脏他的手，他希望最小化操作次数。给定格子颜色的信息、印章的大小以及起点和终点的位置，编写一个程序，计算他为了使存在一条仅由白色格子组成的从起点到终点的路径所必须执行的最少操作次数。

输入格式

从标准输入读取以下数据：

$R \ C \ N$ $S_r \ S_c$ $G_r \ G_c$ $A_1$ $A_2$ $\vdots$ $A_R$

$A_i$ ($1 \le i \le R$) 是一个长度为 $C$ 的字符串，由 . 或 # 组成。$A_i$ 的第 $j$ 个字符（$1 \le j \le C$）表示格子 $(i, j)$ 的颜色。如果字符是 .，则颜色为白色；如果字符是 #，则颜色为黑色。

输出格式

向标准输出打印一行。输出应包含 K 先生为了使存在一条仅由白色格子组成的从起点到终点的路径所必须执行的最少操作次数。

数据范围

• $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) \neq (G_r, G_c)$
• $A_i$ ($1 \le i \le R$) 是一个长度为 $C$ 的字符串，由 . 或 # 组成。
• 格子 $(S_r, S_c)$ 的颜色为白色。
• 格子 $(G_r, G_c)$ 的颜色为白色。
• $R, C, N, S_r, S_c, G_r, G_c$ 均为整数。

子任务

1. (8 分) $N = 1, R \times C \le 1\,500\,000$。
2. (19 分) $R \times C \le 1\,000$。
3. (16 分) 答案小于或等于 $10$，且 $R \times C \le 1\,500\,000$。
4. (19 分) $R \times C \le 60\,000$。
5. (5 分) $R \times C \le 150\,000$。
6. (19 分) $R \times C \le 1\,500\,000$。
7. (8 分) $R \times C \le 3\,000\,000$。
8. (6 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

1

说明 1

如果他选择 $(a, b) = (1, 2)$ 并执行一次操作，格子 $(1, 2), (1, 3), (2, 2), (2, 3)$ 变为白色。此时存在一条从起点到终点仅由白色格子组成的路径。例如，路径 $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4)$ 满足条件。 如果不执行操作，则不存在从起点到终点仅由白色格子组成的路径。因此，输出 1。

样例输入 2

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

样例输出 2

4

样例输入 3

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

样例输出 3

1

样例输入 4

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

样例输出 4

0

说明 4

即使不执行操作，也可能存在一条从起点到终点仅由白色格子组成的路径。