在一家大型博物馆中，展厅被划分为 N 行 M 列的网格布局，位置 (i, j) 表示第 i 行第 j 列的网格位置。

博物馆采购了一台巡查机器人，不断巡查博物馆各个角落的安全状况。某些网格位置，被展品或墙壁占用，巡查机器人无法进入这些网格，如果网格 (i, j) 被占用，则标记为 @，机器人能进入的网格标记为 .。

巡查机器人可以沿四个方向（上、下、左、右）移动，每次沿着同一个方向最少移动 1 个网格，最多移动 K 个网格。如果移动的直线路径上遇到了无法进入的网格，机器人会停在无法进入的网格的前一个可以进入的网格中，当然，机器人不能移动到展厅的边界之外。

请你编程计算出，巡查机器人从起点网格 (S_1, S_2) 移动到目标网格 (E_1, E_2) 所需的最少移动次数。如果无论如何都无法到达目标网格，则输出 -1。

请注意，本题需要你编程求解出机器人的最少移动次数，而非最少经过的网格数。

第 1 行包含三个整数 N, M, K 表示展厅网格的行数、列数和每次移动的最多网格数。

第 2 行包含四个整数 S_1,S_2 和 E_1,E_2，分别表示迷宫的起始网格和目标网格。

接下来 N 行，每行有 M 个字符，表示每个网格机器人能否进入，每个网格的字符为 . 或者 @。

输出一个整数，表示巡查机器人从起点到目标点的最少移动次数。如果无法到达，输出 -1。

样例 1 说明

巡查机器人从网格 (3, 2) 移动到 (3, 4)，可以通过以下 5 次移动完成：

• 从 (3, 2) 向左移动 1 格到 (3, 1)。
• 从 (3, 1) 向上移动 2 格到 (1, 1)。
• 从 (1, 1) 向右移动 2 格到 (1, 3)。
• 从 (1, 3) 向右移动 1 格到 (1, 4)。
• 从 (1, 4) 向下移动 2 格到 (3, 4)。

总计 5 次移动。

数据范围

对于所有的测评数据，满足 1 \leq N, M, K \leq 10^6，N \times M \leq 10^6，1 \leq S_1, E_1 \leq N，1 \leq S_2, E_2 \leq M， (S_1, S_2) \neq (E_1, E_2)。测试数据保证起止点机器人一定可以进入。

月赛广搜25年6月