题目描述

给你一个 $n*m$ 的网格，第 $i$ 行第 $j$ 列的格子编号为 $(i,j)$，正常通行的格子用'.'来表示，障碍用'@'来表示。

和正常的移动不同，身体健硕的你可以每次移动可以在同一方向走走 $1$ 至 $k$ 格

问你最少需要多少步才能从起点 $(r1,c1)$ 走到终点$(r2,c2)$ ，如果不能走到，输出 −1 。

输入格式

第一行，$n,m,k$。 $1<=n,m,k<=1000000, n*m <= 1000000$。

第二行，$r1, c1, r2, c2$。 $1<=r1,r2<=n, 1<=c1,c2<=m。$

接下来是 $n$ 行 $m$ 列的二维网格a[1..n][1..m]，其中a[i][j]是'@'或'.'。

【提示】

本题测试点数据较大，只有约10%的数据满足n*m<=100

输出格式

一个整数。

输入/输出例子1

输入：

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

输出：

5

输入/输出例子2

输入：

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

输出：

2