题目描述

有一个二维网格，从上往下，行的编号从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