Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP2=[list(input().strip()) for i in range(H)]
MAP=[-1]*(H*W)

for i in range(H):
    for j in range(W):
        if MAP2[i][j]==".":
            MAP[i*W+j]=1<<25

def ch(x,y,tf):
    return (x*W+y)*4+tf

def back(x):
    tf=x%4
    x//=4
    return x//W,x%W,tf

Q=deque()
Q.append(ch(x1-1,y1-1,0))
Q.append(ch(x1-1,y1-1,1))
Q.append(ch(x1-1,y1-1,2))
Q.append(ch(x1-1,y1-1,3))
MAP[(x1-1)*W+y1-1]=0

while Q:
    x,y,tf=back(Q.popleft())

    if tf==0:
        if 0<=x+1<H and MAP[(x+1)*W+y]>MAP[x*W+y]:
            for i in range(1,K):
                if 0<=x+i<H and MAP[(x+i)*W+y]>MAP[x*W+y]:
                    MAP[(x+i)*W+y]=MAP[x*W+y]+1
                    Q.append(ch(x+i,y,2))
                    Q.append(ch(x+i,y,3))
                else:
                    break
            else:
                if 0<=x+K<H and MAP[(x+K)*W+y]>MAP[x*W+y]:
                    MAP[(x+K)*W+y]=MAP[x*W+y]+1
                    Q.append(ch(x+K,y,0))
                    Q.append(ch(x+K,y,2))
                    Q.append(ch(x+K,y,3))

    elif tf==1:            
        if 0<=x-1<H and MAP[(x-1)*W+y]>MAP[x*W+y]:
            for i in range(1,K):
                if 0<=x-i<H and MAP[(x-i)*W+y]>MAP[x*W+y]:
                    MAP[(x-i)*W+y]=MAP[x*W+y]+1
                    Q.append(ch(x-i,y,2))
                    Q.append(ch(x-i,y,3))
                else:
                    break

            else:
                if 0<=x-K<H and MAP[(x-K)*W+y]>MAP[x*W+y]:
                    MAP[(x-K)*W+y]=MAP[x*W+y]+1
                    Q.append(ch(x-K,y,1))
                    Q.append(ch(x-K,y,2))
                    Q.append(ch(x-K,y,3))

    elif tf==2:
        if 0<=y+1<W and MAP[x*W+y+1]>MAP[x*W+y]:
            for i in range(1,K):
                if 0<=y+i<W and MAP[x*W+y+i]>MAP[x*W+y]:
                    MAP[x*W+y+i]=MAP[x*W+y]+1
                    Q.append(ch(x,y+i,0))
                    Q.append(ch(x,y+i,1))
                else:
                    break

            else:
                if 0<=y+K<W and MAP[x*W+y+K]>MAP[x*W+y]:
                    MAP[x*W+y+K]=MAP[x*W+y]+1
                    Q.append(ch(x,y+K,0))
                    Q.append(ch(x,y+K,1))
                    Q.append(ch(x,y+K,2))
    else:
        if 0<=y-1<W and MAP[x*W+y-1]>MAP[x*W+y]:
            for i in range(1,K):
                if 0<=y-i<W and MAP[x*W+y-i]>MAP[x*W+y]:
                    MAP[x*W+y-i]=MAP[x*W+y]+1
                    Q.append(ch(x,y-i,0))
                    Q.append(ch(x,y-i,1))
                else:
                    break

            else:
                if 0<=y-K<W and MAP[x*W+y-K]>MAP[x*W+y]:
                    MAP[x*W+y-K]=MAP[x*W+y]+1
                    Q.append(ch(x,y-K,0))
                    Q.append(ch(x,y-K,1))
                    Q.append(ch(x,y-K,3))
            
if MAP[(x2-1)*W+y2-1]==1<<25:
    print(-1)
else:
    print(MAP[(x2-1)*W+y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP2=[list(input().strip()) for i in range(H)]
MAP=[-1]*(H*W)

for i in range(H):
    for j in range(W):
        if MAP2[i][j]==".":
            MAP[i*W+j]=1<<25

def ch(x,y,tf):
    return (x*W+y)*2+tf

def back(x):
    tf=x%2
    x//=2
    return x//W,x%W,tf

Q=deque()
Q.append(ch(x1-1,y1-1,0))
Q.append(ch(x1-1,y1-1,1))
MAP[(x1-1)*W+y1-1]=0

while Q:
    x,y,tf=back(Q.popleft())

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and MAP[(x+i)*W+y]>MAP[x*W+y]:
                MAP[(x+i)*W+y]=MAP[x*W+y]+1
                Q.append(ch(x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and MAP[(x+K)*W+y]>MAP[x*W+y]:
                MAP[(x+K)*W+y]=MAP[x*W+y]+1
                Q.append(ch(x+K,y,0))
                Q.append(ch(x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and MAP[(x-i)*W+y]>MAP[x*W+y]:
                MAP[(x-i)*W+y]=MAP[x*W+y]+1
                Q.append(ch(x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and MAP[(x-K)*W+y]>MAP[x*W+y]:
                MAP[(x-K)*W+y]=MAP[x*W+y]+1
                Q.append(ch(x-K,y,0))
                Q.append(ch(x-K,y,1))

    else:
        for i in range(1,K):
            if 0<=y+i<W and MAP[x*W+y+i]>MAP[x*W+y]:
                MAP[x*W+y+i]=MAP[x*W+y]+1
                Q.append(ch(x,y+i,0))
            else:
                break

        else:
            if 0<=y+K<W and MAP[x*W+y+K]>MAP[x*W+y]:
                MAP[x*W+y+K]=MAP[x*W+y]+1
                Q.append(ch(x,y+K,0))
                Q.append(ch(x,y+K,1))

        for i in range(1,K):
            if 0<=y-i<W and MAP[x*W+y-i]>MAP[x*W+y]:
                MAP[x*W+y-i]=MAP[x*W+y]+1
                Q.append(ch(x,y-i,0))
            else:
                break

        else:
            if 0<=y-K<W and MAP[x*W+y-K]>MAP[x*W+y]:
                MAP[x*W+y-K]=MAP[x*W+y]+1
                Q.append(ch(x,y-K,0))
                Q.append(ch(x,y-K,1))
            
if MAP[(x2-1)*W+y2-1]==1<<25:
    print(-1)
else:
    print(MAP[(x2-1)*W+y2-1])

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<25
        else:
            MAP[i][j]=-1

def ch(x,y,tf):
    return (x*W+y)*2+tf

def back(x):
    tf=x%2
    x//=2
    return x//W,x%W,tf

Q=deque()
Q.append(ch(x1-1,y1-1,0))
Q.append(ch(x1-1,y1-1,1))
MAP[x1-1][y1-1]=0

while Q:
    x,y,tf=back(Q.popleft())

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and MAP[x+i][y]>MAP[x][y]:
                MAP[x+i][y]=MAP[x][y]+1
                Q.append(ch(x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and MAP[x+K][y]>MAP[x][y]:
                MAP[x+K][y]=MAP[x][y]+1
                Q.append(ch(x+K,y,0))
                Q.append(ch(x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and MAP[x-i][y]>MAP[x][y]:
                MAP[x-i][y]=MAP[x][y]+1
                Q.append(ch(x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and MAP[x-K][y]>MAP[x][y]:
                MAP[x-K][y]=MAP[x][y]+1
                Q.append(ch(x-K,y,0))
                Q.append(ch(x-K,y,1))

    else:
        for i in range(1,K):
            if 0<=y+i<W and MAP[x][y+i]>MAP[x][y]:
                MAP[x][y+i]=MAP[x][y]+1
                Q.append(ch(x,y+i,0))
            else:
                break

        else:
            if 0<=y+K<W and MAP[x][y+K]>MAP[x][y]:
                MAP[x][y+K]=MAP[x][y]+1
                Q.append(ch(x,y+K,0))
                Q.append(ch(x,y+K,1))

        for i in range(1,K):
            if 0<=y-i<W and MAP[x][y-i]>MAP[x][y]:
                MAP[x][y-i]=MAP[x][y]+1
                Q.append(ch(x,y-i,0))
            else:
                break

        else:
            if 0<=y-K<W and MAP[x][y-K]>MAP[x][y]:
                MAP[x][y-K]=MAP[x][y]+1
                Q.append(ch(x,y-K,0))
                Q.append(ch(x,y-K,1))
            
if MAP[x2-1][y2-1]==1<<25:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<25
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
Q.append((x1-1,y1-1,1))
MAP[x1-1][y1-1]=0

while Q:
    x,y,tf=Q.popleft()

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and 0<=y<W and MAP[x+i][y]>MAP[x][y]:
                MAP[x+i][y]=MAP[x][y]+1
                Q.append((x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and 0<=y<W and MAP[x+K][y]>MAP[x][y]:
                MAP[x+K][y]=MAP[x][y]+1
                Q.append((x+K,y,0))
                Q.append((x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and 0<=y<W and MAP[x-i][y]>MAP[x][y]:
                MAP[x-i][y]=MAP[x][y]+1
                Q.append((x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and 0<=y<W and MAP[x-K][y]>MAP[x][y]:
                MAP[x-K][y]=MAP[x][y]+1
                Q.append((x-K,y,0))
                Q.append((x-K,y,1))

    else:
        for i in range(1,K):
            if 0<=x<H and 0<=y+i<W and MAP[x][y+i]>MAP[x][y]:
                MAP[x][y+i]=MAP[x][y]+1
                Q.append((x,y+i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y+K<W and MAP[x][y+K]>MAP[x][y]:
                MAP[x][y+K]=MAP[x][y]+1
                Q.append((x,y+K,0))
                Q.append((x,y+K,1))

        for i in range(1,K):
            if 0<=x<H and 0<=y-i<W and MAP[x][y-i]>MAP[x][y]:
                MAP[x][y-i]=MAP[x][y]+1
                Q.append((x,y-i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y-K<W and MAP[x][y-K]>MAP[x][y]:
                MAP[x][y-K]=MAP[x][y]+1
                Q.append((x,y-K,0))
                Q.append((x,y-K,1))
            
if MAP[x2-1][y2-1]==1<<25:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<25
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
Q.append((x1-1,y1-1,1))
MAP[x1-1][y1-1]=0

while Q:
    x,y,tf=Q.pop()

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and 0<=y<W and MAP[x+i][y]>MAP[x][y]:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and 0<=y<W and MAP[x+K][y]>MAP[x][y]:
                MAP[x+K][y]=MAP[x][y]+1
                Q.appendleft((x+K,y,0))
                Q.appendleft((x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and 0<=y<W and MAP[x-i][y]>MAP[x][y]:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and 0<=y<W and MAP[x-K][y]>MAP[x][y]:
                MAP[x-K][y]=MAP[x][y]+1
                Q.appendleft((x-K,y,0))
                Q.appendleft((x-K,y,1))

    else:
        for i in range(1,K):
            if 0<=x<H and 0<=y+i<W and MAP[x][y+i]>MAP[x][y]:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y+K<W and MAP[x][y+K]>MAP[x][y]:
                MAP[x][y+K]=MAP[x][y]+1
                Q.appendleft((x,y+K,0))
                Q.appendleft((x,y+K,1))

        for i in range(1,K):
            if 0<=x<H and 0<=y-i<W and MAP[x][y-i]>MAP[x][y]:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y-K<W and MAP[x][y-K]>MAP[x][y]:
                MAP[x][y-K]=MAP[x][y]+1
                Q.appendleft((x,y-K,0))
                Q.appendleft((x,y-K,1))
            
if MAP[x2-1][y2-1]==1<<25:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
Q.append((x1-1,y1-1,1))
MAP[x1-1][y1-1]=0

while Q:
    x,y,tf=Q.pop()

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and 0<=y<W and MAP[x+i][y]>MAP[x][y]:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and 0<=y<W and MAP[x+K][y]>MAP[x][y]:
                MAP[x+K][y]=MAP[x][y]+1
                Q.appendleft((x+K,y,0))
                Q.appendleft((x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and 0<=y<W and MAP[x-i][y]>MAP[x][y]:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and 0<=y<W and MAP[x-K][y]>MAP[x][y]:
                MAP[x-K][y]=MAP[x][y]+1
                Q.appendleft((x-K,y,0))
                Q.appendleft((x-K,y,1))

    else:
        for i in range(1,K):
            if 0<=x<H and 0<=y+i<W and MAP[x][y+i]>MAP[x][y]:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y+K<W and MAP[x][y+K]>MAP[x][y]:
                MAP[x][y+K]=MAP[x][y]+1
                Q.appendleft((x,y+K,0))
                Q.appendleft((x,y+K,1))

        for i in range(1,K):
            if 0<=x<H and 0<=y-i<W and MAP[x][y-i]>MAP[x][y]:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y-K<W and MAP[x][y-K]>MAP[x][y]:
                MAP[x][y-K]=MAP[x][y]+1
                Q.appendleft((x,y-K,0))
                Q.appendleft((x,y-K,1))
            
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
Q.append((x1-1,y1-1,1))
MAP[x1-1][y1-1]=0

while Q:
    x,y,tf=Q.pop()

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and 0<=y<W and (MAP[x+K][y]==1<<30 or MAP[x+K][y]>MAP[x][y]):
                MAP[x+K][y]=MAP[x][y]+1
                Q.appendleft((x+K,y,0))
                Q.appendleft((x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and 0<=y<W and (MAP[x-K][y]==1<<30 or MAP[x-K][y]>MAP[x][y]):
                MAP[x-K][y]=MAP[x][y]+1
                Q.appendleft((x-K,y,0))
                Q.appendleft((x-K,y,1))

    else:
        for i in range(1,K):
            if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y+K<W and (MAP[x][y+K]==1<<30 or MAP[x][y+K]>MAP[x][y]):
                MAP[x][y+K]=MAP[x][y]+1
                Q.appendleft((x,y+K,0))
                Q.appendleft((x,y+K,1))

        for i in range(1,K):
            if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y-K<W and (MAP[x][y-K]==1<<30 or MAP[x][y-K]>MAP[x][y]):
                MAP[x][y-K]=MAP[x][y]+1
                Q.appendleft((x,y-K,0))
                Q.appendleft((x,y-K,1))
            
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=[]
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.append((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.append((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.append((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.append((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
Q.append((x1-1,y1-1,1))
MAP[x1-1][y1-1]=0

while Q:
    x,y,tf=Q.pop()

    if tf==0:
        for i in range(1,K):
            if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y,1))
            else:
                break
        else:
            if 0<=x+K<H and 0<=y<W and (MAP[x+K][y]==1<<30 or MAP[x+K][y]>MAP[x][y]):
                MAP[x+K][y]=MAP[x][y]+1
                Q.appendleft((x+K,y,0))
                Q.appendleft((x+K,y,1))
            

        for i in range(1,K):
            if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y,1))
            else:
                break

        else:
            if 0<=x-K<H and 0<=y<W and (MAP[x-K][y]==1<<30 or MAP[x-K][y]>MAP[x][y]):
                MAP[x-K][y]=MAP[x][y]+1
                Q.appendleft((x-K,y,0))
                Q.appendleft((x-K,y,1))

    else:
        for i in range(1,K+1):
            if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y+K<W and (MAP[x][y+K]==1<<30 or MAP[x][y+K]>MAP[x][y]):
                MAP[x][y+K]=MAP[x][y]+1
                Q.appendleft((x,y+K,0))
                Q.appendleft((x,y+K,1))

        for i in range(1,K+1):
            if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i,0))
            else:
                break

        else:
            if 0<=x<H and 0<=y-K<W and (MAP[x][y-K]==1<<30 or MAP[x][y-K]>MAP[x][y]):
                MAP[x][y-K]=MAP[x][y]+1
                Q.appendleft((x,y-K,0))
                Q.appendleft((x,y-K,1))
            
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
b=10**6+1
Q.append(x1-1+(y1-1)*b)
MAP[x1-1][y1-1]=0

while Q:
    P=Q.pop()
    y=P//b
    x=P%b

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft(x+i+y*b)
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft(x-i+y*b)
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft(x+(y+i)*b)
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft(x+(y-i)*b)
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=[]
b=10**6+1
bb=b*b
Q.append(0+(x1-1)*b+(y1-1)*bb)
MAP[x1-1][y1-1]=0

while Q:
    P=heapq.heappop(Q)
    y=P//bb
    x=(P%bb)//b
    c=P%b

    if MAP[x][y]<c:
        continue

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+(x+i)*b+y*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+(x-i)*b+y*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+x*b+(y+i)*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+x*b+(y-i)*bb))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
MAP[x1-1][y1-1]=0

while Q:
    x,y,c=Q.pop()
    if MAP[x][y]<c:
        continue

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft((x+i,y,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft((x-i,y,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft((x,y+i,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft((x,y-i,MAP[x][y]+1))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])