Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0

    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K

        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < H and 0 <= nj < W:
            if C[ni][nj] != '@':
                timeninj = time[ni][nj]
                if timeninj[d] > t + 1:
                    q.append((t + 1, ni, nj, d))
                    timeninj[d] = t + 1

        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt

    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0

    while q:
        t, i, j, d = q.pop()

        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < H and 0 <= nj < W:
            if C[ni][nj] != '@':
                timeninj = time[ni][nj]
                if timeninj[d] > t + 1:
                    q.append((t + 1, ni, nj, d))
                    timeninj[d] = t + 1

        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt

    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            q.append((t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                q.appendleft((nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            q.append((t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[10**12] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = []
    for i in range(4):
        heappush(q, (0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = heappop(q)
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                heappush(q, (nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            heappush(q, (t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == 10**12:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[-1] * W for _ in range(H)]
    q = [(0, x1, y1)]
    while q:
        d, i, j = heappop(q)
        if dist[i][j] >= 0: continue
        dist[i][j] = d
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] >= 0: continue
                heappush(q, (d + 1, ni, nj))
    print(dist[x2][y2])

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)