题目描述

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with $H$ east-west rows and $W$ north-south columns. Let $(i,j)$ be the square at the $i$-th row from the north and $j$-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered. The square $(i,j)$ has a lotus leaf on it if $c_{ij}$ is @, and it does not if $c_{ij}$ is ..

In one stroke, Snuke can move between $1$ and $K$ squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square $(x_1,y_1)$ to $(x_2,y_2)$. If the travel from $(x_1,y_1)$ to $(x_2,y_2)$ is impossible, point out that fact.

水黾斯努克生活在一个长方形池塘里，这个池塘可以看作是一个网格，东西方向有 $H$ 行，南北方向有 $W$ 列。假设 $(i,j)$ 是位于北面第 $i$ 行和西面第 $j$ 列的正方形。

有些方格上有荷叶，无法进入。如果 $c_{ij}$ 为"@"，则 $(i,j)$ 方格上有荷叶；如果 $c_{ij}$ 为"."，则 $(i,j)$ 方格上没有荷叶。

在一次下棋中，"斯努克 "可以在 $1$ 和 $K$ （含）之间向北、东、南、西四个方向之一移动。移动不能经过有荷叶的方格。禁止移动到有荷叶的位置或移出池塘。

求斯努克从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 所需的最少步数。如果从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 是不可能的，请指出这一事实。

输入格式

输入内容按以下格式标准输入：

$H$ $W$ $K$
$x_1$ $y_1$ $x_2$ $y_2$
$c_{1,1}c_{1,2}$ $..$ $c_{1,W}$
$c_{2,1}c_{2,2}$ $..$ $c_{2,W}$
$:$
$c_{H,1}c_{H,2}$ $..$ $c_{H,W}$

输出格式

打印 Snuke 从正方形 $(x_1,y_1)$ 到 $(x_2,y_2)$ 所需的最少笔画数，如果不可能，则打印 -1。

样例 #1

样例输入 #1

3 5 2
3 2 3 4
.....
.@..@
..@..

样例输出 #1

5

样例 #2

样例输入 #2

1 6 4
1 1 1 6
......

样例输出 #2

2

样例 #3

样例输入 #3

3 3 1
2 1 2 3
.@.
.@.
.@.

样例输出 #3

-1

说明

数据规模与约定

• $1 \leq H,W,K \leq 10^6$
• $H \times W \leq 10^6$
• $1 \leq x_1,x_2 \leq H$
• $1 \leq y_1,y_2 \leq W$
• $x_1 \neq x_2$ 或 $y_1 \neq y_2$ 。
• $c_{i,j}$ 是 . 或 @。
• $c_{x_1,y_1} =$ .
• $c_{x_2,y_2} =$ .
• 输入的所有数字都是整数。

样例 $1$ 解释

最初，斯努克位于 $(3,2)$ 方格。他可以通过以下五步到达方格 $(3, 4)$ ：

• 从 $(3, 2)$ 向西走一格，到达 $(3, 1)$ 。

• 从 $(3, 1)$ 向北走两格，到达 $(1, 1)$ 。

• 从 $(1, 1)$ 向东两格，至 $(1, 3)$ 。

• 从 $(1, 3)$ 向东走一格至 $(1, 4)$ 。

• 从 $(1, 4)$ 向南两格，至 $(3, 4)$ 。