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.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Data structures

Graph traversal

Shortest paths


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())


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
				elif 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:
		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):
				break
			elif dp[e][f] > dp[x][y] + 1:
				dp[e][f] = dp[x][y] + 1
				q.append((e, f))
ans = dp[x2][y2]
if ans == float('infinity'):
	ans = -1
print(ans)


from sys import *
f = lambda : map(int, input().split())
(n, m, k) = f()
t = [[1000000000.0 * (q == '.') for q in stdin.readline()] for i in range(n)]
t.append([0] * m)
(a, b, c, d) = [q - 1 for q in f()]
u = [(a, b)]
t[a][b] = l = 0

def g(i, x, y):
	if i > k or t[x][y] < l:
		return 0
	if t[x][y] > l:
		t[x][y] = l
		v.append((x, y))
	return 1
while u and t[c][d] == 1000000000.0:
	l += 1
	v = []
	for (x, y) in u:
		i = j = 1
		while g(i, x - i, y):
			i += 1
		while g(j, x + j, y):
			j += 1
		i = j = 1
		while g(i, x, y - i):
			i += 1
		while g(j, x, y + j):
			j += 1
	u = v
print(l if t[c][d] < 1000000000.0 else -1)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
(n, m, k) = mp()
l = []
now = [INF for i in range(m)]
distance = []
for i in range(n):
	cur = list(now)
	s = st()
	l.append(s)
	distance.append(cur)
(a, b, c, d) = mp()
(a, b, c, d) = (a - 1, b - 1, c - 1, d - 1)
q = deque()
q.append((a, b))
distance[a][b] = 0
ans = -1
while q:
	(x, y) = q.popleft()
	if (x, y) == (c, d):
		ans = distance[x][y]
		break
	for i in range(4):
		for j in range(1, k + 1):
			(x1, x2) = (x + j * dx[i], y + j * dy[i])
			if x1 < 0 or x2 < 0 or x1 >= n or (x2 >= m) or (l[x1][x2] == '#') or (distance[x1][x2] < 1 + distance[x][y]):
				break
			elif distance[x1][x2] > 1 + distance[x][y]:
				distance[x1][x2] = 1 + distance[x][y]
				q.append((x1, x2))
pr(ans)


import sys
import io, os
input = sys.stdin.readline
INF = 10 ** 18

def main():
	(h, w, k) = map(int, input().split())
	C = [input().rstrip() for i in range(h)]
	(x1, y1, x2, y2) = map(int, input().split())
	(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
	from collections import deque
	q = deque()
	q.append((x1, y1))
	dist = [[INF] * w for i in range(h)]
	dist[x1][y1] = 0
	while q:
		(x, y) = q.popleft()
		if x == x2 and y == y2:
			print(dist[x][y])
			exit()
		for (dx, dy) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
			for i in range(1, k + 1):
				(nx, ny) = (x + dx * i, y + dy * i)
				if nx < 0 or h <= nx:
					break
				if ny < 0 or w <= ny:
					break
				if C[nx][ny] == '#':
					break
				if dist[nx][ny] <= dist[x][y]:
					break
				if dist[nx][ny] == dist[x][y] + 1:
					continue
				dist[nx][ny] = dist[x][y] + 1
				q.append((nx, ny))
	print(-1)
main()


import sys
from collections import deque
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
grid = []
grid1 = []
grid2 = []
leftyes = []
rightyes = []
upyes = []
downyes = []
for i in range(n):
	grid.append(input())
	grid1.append([-1] * m)
	grid2.append([0] * m)
	leftyes.append([0] * m)
	rightyes.append([0] * m)
	downyes.append([0] * m)
	upyes.append([0] * m)
for i in range(n):
	count = 0
	for j in range(m):
		if grid[i][j] == '.':
			count += 1
		else:
			count = 0
		if count > k:
			leftyes[i][j] = 1
			rightyes[i][j - k] = 1
for i in range(m):
	count = 0
	for j in range(n):
		if grid[j][i] == '.':
			count += 1
		else:
			count = 0
		if count > k:
			upyes[j][i] = 1
			downyes[j - k][i] = 1
(x1, y1, x2, y2) = map(int, input().split())
que = deque([(x1 - 1, y1 - 1, 0)])
grid1[x1 - 1][y1 - 1] = 0
while que:
	(x, y, step) = que.popleft()
	if grid2[x][y]:
		continue
	grid2[x][y] = 1
	if not (x < n - 1 and grid1[x + 1][y] != -1 and (grid1[x + 1][y] <= step)):
		curr = x - 1
		count = 0
		while count < k and curr >= 0 and (grid[curr][y] == '.'):
			if grid1[curr][y] != -1:
				curr -= 1
				count += 1
				continue
			que.append((curr, y, step + 1))
			grid1[curr][y] = step + 1
			curr -= 1
			count += 1
	elif upyes[x][y] and grid1[x - k][y] == -1:
		que.append((x - k, y, step + 1))
		grid1[x - k][y] = step + 1
	if not (x > 0 and grid1[x - 1][y] != -1 and (grid1[x - 1][y] <= step)):
		curr = x + 1
		count = 0
		while count < k and curr <= n - 1 and (grid[curr][y] == '.'):
			if grid1[curr][y] != -1:
				curr += 1
				count += 1
				continue
			que.append((curr, y, step + 1))
			grid1[curr][y] = step + 1
			curr += 1
			count += 1
	elif downyes[x][y] and grid1[x + k][y] == -1:
		que.append((x + k, y, step + 1))
		grid1[x + k][y] = step + 1
	if not (y < m - 1 and grid1[x][y + 1] != -1 and (grid1[x][y + 1] <= step)):
		curr = y - 1
		count = 0
		while count < k and curr >= 0 and (grid[x][curr] == '.'):
			if grid1[x][curr] != -1:
				curr -= 1
				count += 1
				continue
			que.append((x, curr, step + 1))
			grid1[x][curr] = step + 1
			curr -= 1
			count += 1
	elif leftyes[x][y] and grid1[x][y - k] == -1:
		que.append((x, y - k, step + 1))
		grid1[x][y - k] = step + 1
	if not (y > 0 and grid1[x][y - 1] != -1 and (grid1[x][y - 1] <= step)):
		curr = y + 1
		count = 0
		while count < k and curr <= m - 1 and (grid[x][curr] == '.'):
			if grid1[x][curr] != -1:
				curr += 1
				count += 1
				continue
			que.append((x, curr, step + 1))
			grid1[x][curr] = step + 1
			curr += 1
			count += 1
	elif rightyes[x][y] and grid1[x][y + k] == -1:
		que.append((x, y + k, step + 1))
		grid1[x][y + k] = step + 1
print(grid1[x2 - 1][y2 - 1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from math import inf
from collections import deque
for _ in range(int(input()) if not True else 1):
	(n, m, k) = map(int, input().split())
	a = []
	for i in range(n):
		a += [input()]
	(x1, y1, x2, y2) = map(int, input().split())
	(x1, y1) = (x1 - 1, y1 - 1)
	(x2, y2) = (x2 - 1, y2 - 1)
	queue = deque([(x1, y1)])
	dist = [[inf] * m for i in range(n)]
	dist[x1][y1] = 0
	while queue:
		(x, y) = queue.popleft()
		for i in range(x + 1, x + k + 1):
			if i >= n or dist[i][y] <= dist[x][y] or a[i][y] == '#':
				break
			if dist[i][y] == inf:
				queue += [(i, y)]
			dist[i][y] = dist[x][y] + 1
		for i in range(x - 1, x - k - 1, -1):
			if i < 0 or dist[i][y] <= dist[x][y] or a[i][y] == '#':
				break
			if dist[i][y] == inf:
				queue += [(i, y)]
			dist[i][y] = dist[x][y] + 1
		for j in range(y + 1, y + k + 1):
			if j >= m or dist[x][j] <= dist[x][y] or a[x][j] == '#':
				break
			if dist[x][j] == inf:
				queue += [(x, j)]
			dist[x][j] = dist[x][y] + 1
		for j in range(y - 1, y - k - 1, -1):
			if j < 0 or dist[x][j] <= dist[x][y] or a[x][j] == '#':
				break
			if dist[x][j] == inf:
				queue += [(x, j)]
			dist[x][j] = dist[x][y] + 1
	print(-1 if dist[x2][y2] == inf else dist[x2][y2])