题目描述

有一天，Dancho 弄丢了他的麻雀。麻雀非常聪明，想要回到 Dancho 身边，而 Dancho 只是决定躺着等它回来。

现在 Dancho 和麻雀位于一个有 $R$ 行 $C$ 列的网格中。某些格子里有人，麻雀害怕经过这些格子，因此它只会在空格子之间移动。

由于只走空格子并不总是能回到 Dancho 身边，麻雀决定使用自己的特殊能力：它可以选择一个 $N \times N$ 的子矩形，并把其中所有人都赶走。也就是说，这个 $N \times N$ 的正方形区域内的所有格子都会变成可以通过的空格子。

麻雀经历了很多事情后已经非常疲惫，因此它想知道最少需要使用多少次这种特殊能力，才能使自己能够到达 Dancho 所在的位置。

请编写程序 lost，帮助它回答这个问题。

输入格式

第一行输入三个整数 $R,C,N$，分别表示网格的行数、列数，以及麻雀一次可以清空的正方形边长。

第二行输入两个整数 $S_r,S_c$，表示麻雀初始所在的行和列。

第三行输入两个整数 $G_r,G_c$，表示 Dancho 所在的行和列。

接下来 $R$ 行，每行一个长度为 $C$ 的字符串，描述网格：

• # 表示该格子中有人；
• . 表示该格子为空，可以通过。

行列编号均从 $1$ 开始。

输出格式

输出一行一个整数，表示为了让麻雀能够到达 Dancho，最少需要使用特殊能力的次数。

数据范围

• $1 \le N \le R,C$
• $R \times C \le 6 \times 10^6$
• $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)$
• 起点 $(S_r,S_c)$ 和终点 $(G_r,G_c)$ 所在格子都没有人。

子任务

只有通过某个子任务的所有测试点，才能获得该子任务分数。

样例 1

输入

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

输出

1

样例 2

输入

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

输出

4