水黾

题目描述

水黾すぬけ君住在一个南北 $H$ 格、东西 $W$ 格的长方形网格状池塘里。将从北数第 $i$ 格、从西数第 $j$ 格称为格子 $(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} \ldots c_{1,W}$
$c_{2,1}c_{2,2} \ldots c_{2,W}$
$:$
$c_{H,1}c_{H,2} \ldots c_{H,W}$

输出格式

输出すぬけ君从格子 $(x_1,y_1)$ 移动到格子 $(x_2,y_2)$ 所需的最少划水次数。 如果无法从 $(x_1,y_1)$ 移动到 $(x_2,y_2)$,输出 -1。

样例

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

5

最初,すぬけ君在格子 $(3,2)$。 通过以下方式划 $5$ 次水,可以移动到格子 $(3,4)$:

• 从格子 $(3,2)$ 向西移动 $1$ 格,到达格子 $(3,1)$。
• 从格子 $(3,1)$ 向北移动 $2$ 格,到达格子 $(1,1)$。
• 从格子 $(1,1)$ 向东移动 $2$ 格,到达格子 $(1,3)$。
• 从格子 $(1,3)$ 向东移动 $1$ 格,到达格子 $(1,4)$。
• 从格子 $(1,4)$ 向南移动 $2$ 格,到达格子 $(3,4)$。

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

2

3 3 1
2 1 2 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} =$ .
• 输入的所有数值均为整数。