Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks. Formally, her room can be represented as a field of $n \times m$ cells, each cell of which is empty or littered with cans. Olya drank a lot of energy drink, so now she can run $k$ meters per second. Each second she chooses one of the four directions (up, down, left or right) and runs from $1$ to $k$ meters in this direction. Of course, she can only run through empty cells. Now Olya needs to get from cell $(x_1, y_1)$ to cell $(x_2, y_2)$. How many seconds will it take her if she moves optimally? It's guaranteed that cells $(x_1, y_1)$ and $(x_2, y_2)$ are empty. These cells can coincide. --- Olya 特别喜欢喝能量饮料，以至于她的房间里全都是空瓶子。 Olya 的房间可以描述为一张 $n \times m$ 的网格图，每个网格里要么是空的，要么有一些空瓶子。 Olya 喝了很多的能量饮料，所以她每秒钟可以任意选择四个方向（上、下、左、右）中的一个，行走至多 $k$ 步的距离。她只能在空的网格内行走。 现在 Olya 想从位置 $(x_1, y_1)$ 走到位置 $(x_2, y_2)$，试问至少需要多少秒时间？ 保证位置 $(x_1, y_1)$ 与位置 $(x_2, y_2)$ 都是空的，这两点可能重叠。

The first line contains three integers $n$, $m$ and $k$ $(1 \le n, m, k \le 1000)$ — the sizes of the room and Olya's speed. Then $n$ lines follow containing $m$ characters each, the $i$-th of them contains on $j$-th position `#`, if the cell $(i, j)$ is littered with cans, and `.` otherwise. The last line contains four integers $x_1$, $y_1$, $x_2$, $y_2$ $(1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m)$ — the coordinates of the first and the last cells.

Print a single integer — the minimum time it will take Olya to get from $(x_1, y_1)$ to $(x_2, y_2)$. If it's impossible to get from $(x_1, y_1)$ to $(x_2, y_2)$, print `-1`.

In the first sample Olya should run $3$ meters to the right in the first second, $2$ meters down in the second second and $3$ meters to the left in the third second. In second sample Olya should run to the right for $3$ seconds, then down for $2$ seconds and then to the left for $3$ seconds. *Olya does not recommend drinking energy drinks and generally believes that this is bad.* --- - 本题数据已针对性重造，部分原题解法可能无法通过。 - 如想对标在“第二届ACC(AcWing Cup)全国联赛”赛内通过本题，请保证在本OJ能够得出运行时长在 `200ms` 以内的解法。 - 以 `m` `l` 开头的测试数据组生成算法可见以下附件（虽然对于解题并没有什么用23333） - [🔗3893-lm-Generator.cpp](/userfiles/files/debdac39-4f88-4456-afee-044df0caf8b1.cpp)

Codeforces Div. 2 [CF877D] | 第二届ACC(AcWing Cup)全国联赛