Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks.

Formally, her room can be represented as a field of n × m cells, each cell of which is empty or littered with cans.

Olya drank a lot of energy drink, so now she can run k meters per second. Each second she chooses one of the four directions (up, down, left or right) and runs from 1 to k meters in this direction. Of course, she can only run through empty cells.

Now Olya needs to get from cell (x_1, y_1) to cell (x_2, y_2). How many seconds will it take her if she moves optimally?

It's guaranteed that cells (x_1, y_1) and (x_2, y_2) are empty. These cells can coincide.


-----Input-----

The first line contains three integers n, m and k (1 ≤ n, m, k ≤ 1000) — the sizes of the room and Olya's speed.

Then n lines follow containing m characters each, the i-th of them contains on j-th position "#", if the cell (i, j) is littered with cans, and "." otherwise.

The last line contains four integers x_1, y_1, x_2, y_2 (1 ≤ x_1, x_2 ≤ n, 1 ≤ y_1, y_2 ≤ m) — the coordinates of the first and the last cells.


-----Output-----

Print a single integer — the minimum time it will take Olya to get from (x_1, y_1) to (x_2, y_2).

If it's impossible to get from (x_1, y_1) to (x_2, y_2), print -1.


-----Examples-----
Input
3 4 4
....
###.
....
1 1 3 1

Output
3
Input
3 4 1
....
###.
....
1 1 3 1

Output
8
Input
2 2 1
.#
#.
1 1 2 2

Output
-1


-----Note-----

In the first sample Olya should run 3 meters to the right in the first second, 2 meters down in the second second and 3 meters to the left in the third second.

In second sample Olya should run to the right for 3 seconds, then down for 2 seconds and then to the left for 3 seconds.

Olya does not recommend drinking energy drinks and generally believes that this is bad.

Difficulty: interview

Starter code:

Solutions:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m,k = LI()
    a = [[-1] * (m+2)]
    a += [[-1] + [inf if c=='.' else -1 for c in S()] + [-1] for _ in range(n)]
    a += [[-1] * (m+2)]
    x1,y1,x2,y2 = LI()
    a[x1][y1] = 0
    q = [(x1,y1)]
    qi = 0
    dy = [-1,1,0,0]
    dx = [0,0,-1,1]
    while qi < len(q):
        x,y = q[qi]
        qi += 1
        nd = a[x][y] + 1
        for di in range(4):
            for j in range(1,k+1):
                ny = y + dy[di] * j
                nx = x + dx[di] * j
                if a[nx][ny] > nd:
                    if ny == y2 and nx == x2:
                        return nd
                    a[nx][ny] = nd
                    q.append((nx,ny))
                elif a[nx][ny] < nd:
                    break

    if a[x2][y2] < inf:
        return a[x2][y2]
    return -1


print(main())




import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def main():
    n,m,k = LI()
    a = [[-1] * (m+2)]
    a += [[-1] + [inf if c=='.' else -1 for c in S()] + [-1] for _ in range(n)]
    a += [[-1] * (m+2)]
    x1,y1,x2,y2 = LI()
    a[x1][y1] = 0
    q = [(x1,y1)]
    qi = 0
    dy = [-1,1,0,0]
    dx = [0,0,-1,1]
    while qi < len(q):
        x,y = q[qi]
        qi += 1
        nd = a[x][y] + 1
        for di in range(4):
            for j in range(1,k+1):
                ny = y + dy[di] * j
                nx = x + dx[di] * j
                if a[nx][ny] > nd:
                    if ny == y2 and nx == x2:
                        return nd
                    a[nx][ny] = nd
                    q.append((nx,ny))
                elif a[nx][ny] < nd:
                    break
    if a[x2][y2] < inf:
        return a[x2][y2]
    return -1
print(main())


from collections import deque
n, m, k = map(int, input().split())
INF = float("inf")
d = [[INF] * m for _ in range(n)]
t = [[] for i in range(n)]
for i in range(n):
    a = list(input())
    t[i] = a

sx, sy, gx, gy = map(int, input().split())
sx, sy, gx, gy = sx - 1, sy - 1, gx - 1, gy - 1


def bfs():
    que = deque()
    que.append((sx, sy))
    d[sx][sy] = 0

    while len(que):
        x, y = que.popleft()
        if x == gx and y == gy:
            break
        for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            for i in range(1, k + 1):
                nx, ny = x + i * dx, y + i * dy
                if not 0 <= nx < n or not 0 <= ny < m or t[nx][ny] != "." or d[nx][ny] <= d[x][y]:
                    break
                else:
                    if d[nx][ny] > d[x][y] + 1:
                        d[nx][ny] = d[x][y] + 1
                        que.append((nx, ny))

    return d[gx][gy]


ans = bfs()
if ans == INF:
    print(-1)
else:
    print(ans)

from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
from collections import deque
n,m,k=list(map(int,input().split()))
dp=[[float("infinity") for i in range(m)] for i in range(n)]
l=[]
for i in range(n):
	l.append(list(input()))
x1,y1,x2,y2=[int(a)-1 for a in input().split()]
t=[(1,0),(0,1),(0,-1),(-1,0)]
q=deque()
q.append((x1,y1))
dp[x1][y1]=0
while q:
	x,y=q.popleft()
	if x==x2 and y==y2:
		# print(90)
		break
	for a,b in t:
		for i in range(1,k+1):
			e=x+i*a
			f=y+i*b
			if e<0 or e>=n or f>=m or f<0 or l[e][f]!="." or dp[e][f]<dp[x][y]+1:
				# print(e,f)
				break
			else:
				if dp[e][f]>dp[x][y]+1:
					dp[e][f]=dp[x][y]+1
					q.append((e,f))
	# print(q)
ans=dp[x2][y2]
if ans==float("infinity"):
	ans=-1
print(ans)