### 问题描述 小蓝有一天误入了一个混境之地。 好消息是：他误打误撞拿到了一张地图，并从中获取到以下信息： 1. 混境之地的大小为 $n \cdot m$，其中 `#` 表示不可通过的墙壁，`.` 表示可以走的路。 2. 他现在所在位置的坐标为 $(A, B)$ ，而这个混境之地出口的坐标为 $(C, D)$ ，当静止在出口时即表示可以逃离混境之地。 坏消息是： 1. 受强大磁场影响，小蓝每次行动，必须移动 $k$ 步。 小蓝每步都可以往上下左右四个方向行走。禁止原地踏步，但是允许走已经走过的路。 小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，则输入最少需要行动的次数，反之输出 `-1` 。 请注意本题中 **行动次数** 与 **步数** 的区别，另外只有行动结束时小蓝在终点上，才算成功逃离。 ### 输入格式 第 $1$ 行输入两个正整数 $n, m$ ，表示混境之地的大小。 第 $2$ 行输入四个正整数 $A, B, C, D$ ，表示小蓝当前所在位置的坐标，以及混境之地出口的坐标。 第 $3$ 行至第 $n + 2$ 行，每行 $m$ 个字符，表示混境之地的地图，其中 `#` 表示不可通过的墙壁， `.` 表示普通的道路。 最后一行输入一个正整数 $k$ ，表示小蓝每次行动必须移动的步数。 ### 输出格式 输出数据共一行为一个整数： - 若小蓝可以逃离混境之地，则输出最少需要行动的次数。 - 若小蓝无法逃离混境之地，则输出 `-1` 。 ### 样例输入1 ```txt 5 5 1 1 5 5 ...#. ..#.. #...# ..... ...#. 1 ``` ### 样例输出1 ```txt 8 ``` ### 样例解释1  如图所示，绿色方块表示可以走的路，红色方块表示墙，蓝色圆圈小蓝当前所在的位置，橙色圆圈为终点。 从 $(1, 1)$ 到 $(5, 5)$ 的一条最短道路为： $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (4, 4) \rightarrow (4, 5) \rightarrow (5, 5)$ 。 ### 样例输入2 ```txt 5 5 1 1 5 5 ...#. ..#.. #...# ..... ...#. 3 ``` ### 样例输出2 ```txt 4 ``` ### 样例解释2 图如样例 $1$ 所示。 从 $(1, 1)$ 到 $(5, 5)$ 的一条可行最短道路为： $(1, 1) \rightarrow [(1, 2) \rightarrow (2, 2) \rightarrow (3, 2)] \rightarrow [(4, 2) \rightarrow (5, 2) \rightarrow (5, 3)] \rightarrow [(4, 3) \rightarrow (3, 3) \rightarrow (3, 4)] \rightarrow [(4, 4) \rightarrow (4, 5) \rightarrow (5, 5)]$ 。其中一个 $[$ $]$ 的内容为一次行动。 ### 数据范围 对于所有测试样例， $1 \leq n, m \leq 1000$ 。 数据保证起点和终点均不为墙。