题目描述

有一个二维网格，从上往下，行的编号从 $1$ 至 $n$ ，从左往右，列的编号是 $1$ 至 $m$。

第 $i$ 行第 $j$ 列的格子编号为($i,j$)，如果 $a[i][j]$ 为 '@' ,表示格子($i,j$)有障碍物，如果 $a[i][j]$ 为 '.' 则表示格子 ($i,j$) 可通行。

奶牛 Bessie 当前在 格子($r_1,c_1$)，它每一步可以选择往上、下、左、右四个方向之一走 $1$ 至 $k$ 格，也就是每一步至少走 $1$ 格，最多可以走 $k$ 格。

任何时刻都不能进入障碍物格子，也不能走到网格外面，不能走出界。

问你最少需要多少步才能走到 格子($r_2,c_2$) ，如果不能走到，输出 $−1$ 。

输入格式

第一行，$n,m,k$ ( $1 \le n,m,k \le 10^6$, $n*m \le 10^6$ )；

第二行，$r_1, c_1, r_2, c_2$ ( $1 \le r_1,r_2 \le n$, $1 \le c_1,c_2 \le m$ )；

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

提示

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

输出格式

一个整数。

样例

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

5

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

2