Olya 喜欢能量饮料。她非常喜欢它们,以至于她的房间里堆满了能量饮料的空罐。
从形式上来说,她的房间可以表示为一个由 n × m 个单元格组成的区域,每个单元格都是空的或散落着罐头。
Olya 喝了很多能量饮料,所以现在她每秒可以跑 k 米。每一秒,她都会选择四个方向(上、下、左或右)之一,并沿该方向跑 1 米到 k 米。当然,她只能穿过空荡荡的牢房。
现在 Olya 需要从单元格 (x1, y1) 到达单元格 (x2, y2)。如果她的动作达到最佳状态,需要多少秒?
保证单元格 (x1, y1) 和 (x2, y2) 为空。这些单元可以重合。
输入
第一行包含三个整数 n、m 和 k (1 ≤ n, m, k ≤ 1000) — 房间的大小和 Olya 的速度。
接下来的 n 行每行包含 m 个字符,其中第 i 行在第 j 个位置上包含“#”,如果单元格 (i, j) 中散布着罐头,则第 i 行包含“.”。否则。
最后一行包含四个整数 x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — 第一个和最后一个单元格的坐标。
输出
打印一个整数——Olya 从 (x1, y1) 到 (x2, y2) 所需的最短时间。
如果无法从 (x1, y1) 到达 (x2, y2),则打印 -1。
示例
输入 #1
3 4 4 .... ###. .... 1 1 3 1
输出 #1
3
输入 #2
3 4 1 .... ###. .... 1 1 3 1
输出 #2
8
输入 #3
2 2 1 .# #. 1 1 2 2
输出 #3
-1
注意
在第一个示例中,Olya 应在第一秒内向右跑 3 米,在第二秒内向下跑 2 米,在第三秒内向左跑 3 米。
在第二个示例中,Olya 应向右跑 3 秒,然后向下跑 2 秒,然后向左跑 3 秒。
Olya不建议喝能量饮料,并且普遍认为这不好。