题目描述

Snuke是一只水黾，它生活在一个可以看作是$H$行$W$列的方形池塘中。用$(i,j)$表示位于北边第$i$行、西边第$j$列的方格。

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

Snuke每次可以朝四个方向之一（北、东、南、西）移动$1$到$K$个方格（包括$1$和$K$）。移动过程中不能经过有荷叶的方格，也不能离开池塘。

找出Snuke从方格$(x_1,y_1)$到$(x_2,y_2)$所需的最小移动次数。如果从$(x_1,y_1)$到$(x_2,y_2)$的移动不可能，指出这个事实。

约束条件

• $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} =$ .
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出输入数据：

$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

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

示例输出1

5

初始时，Snuke位于方格$(3,2)$。它可以通过以下五个步骤到达方格$(3,4)$：

• 从$(3,2)$向西移动一个方格到$(3,1)$。

• 从$(3,1)$向北移动两个方格到$(1,1)$。

• 从$(1,1)$向东移动两个方格到$(1,3)$。

• 从$(1,3)$向东移动一个方格到$(1,4)$。

• 从$(1,4)$向南移动两个方格到$(3,4)$。

示例输入2

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

示例输出2

2

示例输入3

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

示例输出3

-1