该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

如果a[i][j]为'.'则表示格子(i,j)可通行。

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

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

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

输入格式

第一行，n,m,k。 1<=n,m,k<=1000000, n*m <= 1000000。

第二行，r1, c1, r2, c2。 1<=r1,r2<=n, 1<=c1,c2<=m。

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

【提示】

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

输出格式

一个整数。

输入/输出例子1

输入：

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

输出：

5

输入/输出例子2

输入：

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

输出：

2