配点 : $600$ 点

問題文

アメンボのすぬけ君は南北 $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)$ まで移動することができない場合、そのことを指摘してください。

制約

• $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}$

出力

すぬけ君がマス $(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