题目描述

有一个 $n$ 行 $m$ 列的网格。. 表示可以通行，@ 表示障碍。给定起点 $ (s_1,s_2) $ 和终点 $ (e_1,e_2) $，请计算从起点到终点所需的最少移动次数。

每次移动选择上、下、左、右中的一个方向，并沿该方向移动 $1$ 至 $k$ 个格子。一次移动中不能改变方向，也不能经过障碍或越出网格；落脚格必须是可通行格。

输入格式

第一行包含三个整数 $n,m,k$。 第二行包含四个整数 $s_1,s_2,e_1,e_2$，分别表示起点行号、起点列号、终点行号和终点列号，行号范围为 $1$ 到 $n$，列号范围为 $1$ 到 $m$。 接下来 $n$ 行每行包含一个长度为 $m$ 的字符串，描述网格。

输出格式

输出一个整数。若无法到达终点，输出 -1。

样例

3 4 2
1 1 1 4
....
.@@.
....

2

数据范围与提示

• $1 \le n,m \le 1000$
• $1 \le k \le 100$
• 起点和终点均为 .。