喜欢解迷宫的 K 理事长发现了一块看起来像迷宫的格子。这块格子是一个纵向 $R$ 行，横向 $C$ 列的矩形，每个格子被涂成白色或黑色。从上往下第 $i$ 行 ($1 \leq i \leq R$)、从左往右第 $j$ 列 ($1 \leq j \leq C$) 的格子称为格子 $(i, j)$。

K 理事长规定，白色格子可以通行，黑色格子不可通行，并打算以此来解迷宫。具体地说，解迷宫的过程如下所示：

1. 从所有白色格子中选择一个起点格子 $(S_r, S_c)$ 和一个终点格子 $(G_r, G_c)$。
2. 不断移动到上下左右相邻的白色格子，寻找一条从起点到终点仅经过白色格子的路径。

K 理事长注意到，视格子的涂色情况不同，可能根本不存在仅经过白色格子的起点到终点路径。于是，他打算用自己的 $N \times N$ 大小的“印章”反复进行以下操作，使得从起点到终点存在只经过白色格子的路径。

操作：选择格子中的一个 $N \times N$ 大小的正方形区域，将该区域内所有格子全部变为白色。更严格地说，选取满足 $1 \leq a \leq R - N + 1$，$1 \leq b \leq C - N + 1$ 的整数 $a, b$，将所有满足 $a \leq i \leq a + N - 1$、$b \leq j \leq b + N - 1$ 的格子 $(i, j)$ 设为白色。

因为使用“印章”会弄脏手，因此希望操作次数尽可能少。给定格子的初始涂色、印章大小，以及起点和终点的位置，请编写程序，求出使得存在仅经过白色格子的从起点到终点路径所需的最小操作次数。

---

输入从标准输入按如下格式给出。

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

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

输出一个整数，为使得存在仅经过白色格子的从起点到终点路径所需的最小操作次数。

---

子任务

1. (8 分) $N = 1$，$R \times C \leq 1\,500\,000$。
2. (19 分) $R \times C \leq 1\,000$。
3. (16 分) 答案不超过 $10$，$R \times C \leq 1\,500\,000$。
4. (19 分) $R \times C \leq 60\,000$。
5. (5 分) $R \times C \leq 150\,000$。
6. (19 分) $R \times C \leq 1\,500\,000$。
7. (8 分) $R \times C \leq 3\,000\,000$。
8. (6 分) 没有额外限制。

---

样例解释 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, 3, 4, 5, 6, 7, 8$ 的约束。

---

样例解释 2

该输入数据满足所有子任务的约束。

---

样例解释 3

该输入数据满足子任务 $2, 3, 4, 5, 6, 7, 8$ 的约束。

---

样例解释 4

有时即使不进行任何操作，也可能存在仅经过白色格子的从起点到终点路径。

该输入数据满足所有子任务的约束。

约束条件

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

由 ChatGPT 5 翻译