CF877D.Olya and Energy Drinks

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 × 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.

奥莉亚非常喜欢能量饮料。她对能量饮料的喜爱程度如此之高，以至于她的房间里堆满了喝空的能量饮料罐。

形式化地，她的房间可以被表示为一个 $n \times m$ 的网格，其中每个格子要么为空，要么堆有饮料罐。

奥莉亚喝了大量的能量饮料，因此现在她每秒可以奔跑 $k$ 米。每一秒，她选择四个方向之一（上、下、左或右），并沿该方向奔跑 $1$ 至 $k$ 米。当然，她只能穿过空的格子。

现在，奥莉亚需要从格子 $(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 ≤ n, m, k ≤ 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 ≤ _x_1, _x_2 ≤ n, 1 ≤ _y_1, _y_2 ≤ m) — the coordinates of the first and the last cells.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m, k ≤ 1000$）——分别表示房间的尺寸以及奥莉娅的移动速度。

接下来是 $n$ 行，每行包含 $m$ 个字符；其中第 $i$ 行的第 $j$ 个字符为 #，表示单元格 $(i, j)$ 被易拉罐占据；否则为 .。

最后一行包含四个整数 $x_1$、$y_1$、$x_2$、$y_2$（$1 ≤ x_1, x_2 ≤ n$，$1 ≤ y_1, y_2 ≤ m$）——分别表示起点和终点的坐标。

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.

输出一个整数——Olya 从 $(x_1, y_1)$ 到达 $(x_2, y_2)$ 所需的最短时间。

如果无法从 $(x_1, y_1)$ 到达 $(x_2, y_2)$，则输出 $-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.

在第一个样例中，奥莉娅应在第一秒向右跑 3 米，第二秒向下跑 2 米，第三秒向左跑 3 米。

在第二个样例中，奥莉娅应先向右跑 3 秒，再向下跑 2 秒，最后向左跑 3 秒。

奥莉娅不建议饮用能量饮料，且总体上认为这是不好的。