Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = [list(input()) for x in range(h)]

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

while q:
    v = q.popleft()
    count = 0
    for i in m:
        count += i.count("#")
    if count == h*w:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

######
ans = 0
for i in d:
    ans = max(ans,max(i))
print(ans)


### FIXED CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

for i in range(N):
    A_ = [A[j] for j in range(0, N) if i != j]
    print(max(A_))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

FIRST = max(A)
if A.count(FIRST) > 1:
    for i in range(N):
        print(FIRST)
else:
    SECOND = max([a for a in A if a != FIRST])
    for a in A:
        if a == FIRST:
            print(SECOND)
        else:
            print(FIRST)
### BUGGY CODE ###

mod = 10**9 +7
n, a, b = map(int, input().split())

nb = str(bin(n))[2:]
nblis = []
for k in range(len(nb)):
  if nb[-k-1] == '1':
    nblis.append(k)

two = [2]
for k in range(len(nb)-1):
  two.append(two[-1]*two[-1]%mod)


ans = 1
for item in nblis:
  ans = ans * two[item] %mod



bi = str(bin(mod-2))[2:]
blis = []
for k in range(len(bi)):
  if bi[-k-1] == '1':
    blis.append(k)


def modinv(N):
  if N == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(len(bi)):
      li.append(N%mod)
      N = N*N%mod
    for item in blis:
      res = res * li[item] %mod
    return res

ans_a = 1
for k in range(n-a+1, n+1):
  ans_a = ans_a*k%mod
for k in range(2, a+1):
  ans_a = ans_a*modinv(k)%mod


ans_b = 1
for k in range(n-b+1, n+1):
  ans_b = ans_b*k%mod
for k in range(2, b+1):
  ans_b = ans_b*modinv(k)%mod

print((ans-ans_a-ans_b-1)%mod)

### FIXED CODE ###

mod = 10**9 +7
n, a, b = map(int, input().split())

nb = str(bin(n))[2:]
nblis = []
for k in range(len(nb)):
  if nb[-k-1] == '1':
    nblis.append(k)

two = [2]
for k in range(len(nb)-1):
  two.append(two[-1]*two[-1]%mod)


ans = 1
for item in nblis:
  ans = ans * two[item] %mod



bi = str(bin(mod-2))[2:]
blis = []
for k in range(len(bi)):
  if bi[-k-1] == '1':
    blis.append(k)


def modinv(N):
  if N == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(len(bi)):
      li.append(N%mod)
      N = N*N%mod
    for item in blis:
      res = res * li[item] %mod
    return res

ans_a = 1
for k in range(n-a+1, n+1):
  ans_a = ans_a*k%mod
for k in range(2, a+1):
  ans_a = ans_a*modinv(k)%mod


ans_b = 1
for k in range(n-b+1, n+1):
  ans_b = ans_b*k%mod
for k in range(2, b+1):
  ans_b = ans_b*modinv(k)%mod

print((ans-ans_a-ans_b-1)%mod)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = [[] for i in range((n + 2) * n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
not_candidate = set([])
nodes = list(nodes)
for i in nodes:
    if len(adjacent_list[i]) == 0:
        not_candidate.add(i)
        continue
    for j in adjacent_list[i]:
        not_candidate.add(j)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    if i not in not_candidate:
        dfs_path(i)
print(max(max(finish.values()), 1))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))
### BUGGY CODE ###

def getIntList(strList):
  return list(map(lambda x: int(x), strList))

N, M, K = getIntList(input().split(" "))
A = getIntList(input().split(" "))
B = getIntList(input().split(" "))

TA = 0
T = [0]
cnt = [] # idx = n of B books

for i in range(len(A)):
  TA += A[i]
  if TA <= K:
    T.append(TA)
  else:
    break

cnt.append(len(T) - 1)

for j in range(len(B)):
  T = list(filter(lambda t: t<= K, list(map(lambda t: t + B[j], T))))
  cnt.append(len(T) - 1)
  if len(T) <= 0:
    break

for k in range(len(cnt)):
  cnt[k] += k

print(max(cnt))

### FIXED CODE ###

def getIntList(strList):
  return list(map(lambda x: int(x), strList))

N, M, K = getIntList(input().split(" "))
A = getIntList(input().split(" "))
B = getIntList(input().split(" "))

ta = 0
tb = 0
TA = [0]
TB = [0]

for i in range(len(A)):
  ta += A[i]
  if ta <= K:
    TA.append(ta)
  else:
    break
for j in range(len(B)):
  tb += B[j]
  if tb <= K:
    TB.append(tb)
  else:
    break

Cij = [0]

j = len(TB) - 1
for i in range(len(TA)):
  while TA[i] + TB[j] > K:
    j += -1
  else:
    if j >= 0:
      Cij.append(i + j)
  if j == -1:
    break


print(max(Cij))
### BUGGY CODE ###

N, K, Q = map(int, input().split())

L = []

for i in range(Q):
    A = int(input())
    L.append(A)

for i in range(N):
    if K > Q - L.count(i+1):
        print('Yes')
    else:
        print('No')  

### FIXED CODE ###

N, K, Q = map(int, input().split())

L = [K]*N

for i in range(Q):
    A = int(input())
    L[A-1] += 1

for i in L:
    if i - Q > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,M=rl()

if M%N==0:
    print(M//N)
else:
    x = M//N
    ans = 1
    for i in range(x,0,-1):
        if M%i != 0:
            continue
        else:
            if M//i >= N:
                ans = i
                break
    
    print(ans)

### FIXED CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,M=rl()

if M%N==0:
    print(M//N)
else:
    x = M//N
    ans = 1
    for i in range(x,0,-1):
        if M%i != 0:
            continue
        else:
            ans = i
            break
    print(ans)
### BUGGY CODE ###

mod = 10**9+7 #出力の制限
def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def resolve():
    n,a,b=map(int,input().split())
    sm=pow_r(2,n)-1

    aa=cmb(n,a)%mod
    bb=cmb(n,b)%mod
    sm-=aa
    if sm<0:
        sm+=mod
    sm-=bb
    if sm<0:
        sm+=mod
    
    print(sm)
    







if __name__ == "__main__":
    resolve()

### FIXED CODE ###

mod = 10**9+7 #出力の制限
def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    g1=1
    r = min(r, n-r)
    for i in range(n-r+1,n+1):
        g1*=i
        g1%=mod



    return g1 * g2[r] % mod


g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
def getgen(N):
    for i in range( 2, N + 1 ):

        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )




def resolve():
    n,a,b=map(int,input().split())
    sm=pow_r(2,n)-1
    getgen(max(a,b))
    aa=cmb(n,a,mod)
    bb=cmb(n,b,mod)

    sm-=aa

    if sm<0:
        sm+=mod
    sm-=bb
    if sm<0:
        sm+=mod
    
    print(sm)
    







if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
P = 1

for k in range(K):
  P*=A[k]
B+=[P]

for n in range(N-K):
  P = P/A[n]*A[n+K]
  B+=[P]
  
  if B[n]<B[n+1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

from numpy import *
N,K = map(int,input().split())
A = log(array(list(map(int,input().split()))))
B = [sum(A[:K])]

for n in range(N-K):
  B+=[B[-1]+A[n+K]-A[n]]
  
  if B[n]<B[n+1]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    a, *ret = sys.stdin.readline().rstrip()
    ret.insert(0, a)
    Q = int(sys.stdin.readline().rstrip())

    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            ret.reverse()
        elif line[0] == '2' and line[1] == '1':
            ret.insert(0, line[2])
        else:
            ret.append(line[2])

    print("".join(ret))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    ret = sys.stdin.readline().rstrip()
    Q = int(sys.stdin.readline().rstrip())
    m = ""
    u = ""
    r = 0
    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            m, u = u, m
            r ^= 1
        elif line[0] == '2' and line[1] == '1':
            m += line[2]
        else:
            u += line[2]

    if r == 0:
        print(m[::-1] + ret[::1] + u)
    else:
        print(m[::-1] + ret[::-1] + u)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

rev_flag = 0

for i in range(Q):
    if Query[i][0] == '1':
        rev_flag = (rev_flag + 1) % 2
    if Query[i][0] == '2':
        if Query[i][1] == '1':
            if rev_flag == 0:
                S = Query[i][2] + S
            elif rev_flag == 1:
                S = S + Query[i][2]
        elif Query[i][1] == '2':
            if rev_flag == 1:
                S = Query[i][2] + S
            elif rev_flag == 0:
                S = S + Query[i][2]

if rev_flag == 1:
    S = S[::-1]

print(S)


### FIXED CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

rev_flag = 0

bef = ''
aft = ''

for i in range(Q):
    if Query[i][0] == '1':
        rev_flag = (rev_flag + 1) % 2
    if Query[i][0] == '2':
        if Query[i][1] == '1':
            if rev_flag == 0:
                bef = Query[i][2] + bef
            elif rev_flag == 1:
                aft = aft + Query[i][2]
        elif Query[i][1] == '2':
            if rev_flag == 1:
                bef = Query[i][2] + bef
            elif rev_flag == 0:
                aft = aft + Query[i][2]

S = bef + S + aft
if rev_flag == 1:
    S = S[::-1]

print(S)
### BUGGY CODE ###

from numpy import*
B=searchsorted
a,b=loadtxt(open(0),skiprows=1)
c=0
l=1<<29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l>>=1;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

n =int(input())
A=[]
for I in range(n):
  moji=input()
  moji=list(moji)
  moji.sort()
  moji=''.join(moji)
  A.append(moji)
N=0
for i in range(n):
  a=A[i]
  for s in range(i+1,n,1):
    b=A[s]
    if a==b:
      N+=1
print(N)

### FIXED CODE ###

n =int(input())
A=[]
for I in range(n):
  moji=list(input())
  moji.sort()
  moji=''.join(moji)
  A.append(moji)
A.sort()
N=0
SUM=0
i=0
while True:
  if i==n-1:
    SUM=SUM+int(0.5*N*(N+1))
    break
  a=A[i]
  for s in range(i+1,n,1):
    b=A[s]
    if a==b:
      N+=1
      i+=1
    else:
      SUM=SUM+int(0.5*N*(N+1))
      N=0
      i=s
      break
print(SUM)
### BUGGY CODE ###

N = int(input())
p_list = list(map(float, input().split()))

dp = [[0.0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[1][1] = p_list[0]
dp[1][0] = 1 - p_list[0]

for i in range(2, N + 1):
    for j in range(i + 1):
        dp[i][j] = p_list[i - 1] * dp[i - 1][j - 1] + (1 - p_list[i - 1]) * dp[i - 1][j]

print("{:.10f}".format(sum(dp[N][N // 2 + 1:])))



### FIXED CODE ###

N = int(input())
p_list = list(map(float, input().split()))

dp = [[0.0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[1][1] = p_list[0]
dp[1][0] = 1 - p_list[0]

for i in range(2, N + 1):
    for j in range(i + 1):
        dp[i][j] = p_list[i - 1] * dp[i - 1][j - 1] + (1 - p_list[i - 1]) * dp[i - 1][j]

print("{:.10f}".format(sum(dp[N][N // 2 + 1:])))
### BUGGY CODE ###

from collections import Counter
n=int(input())
s = [0]*n
for i in range(n):
    s[i]=input()
d = Counter(s)
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()
for i in max_k_list:
    print(i)

### FIXED CODE ###

n=int(input())
d={}
for i in range(n):
    tmp = input()
    if tmp in d:
        d[tmp]+=1
    else:
        d[tmp]=1
max_k_list=[]
max_d = max(d.values())
for k,v in d.items():
    if v == max_d:
        max_k_list.append(k)
max_k_list.sort()
for i in max_k_list:
    print(i)
### BUGGY CODE ###

mod = 10**9+7
def comb_mod(n,r,mod):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans
def solve():
    N, K = map(int, input().split())
    ans = []
    for i in range(1,K+1):
        ans.append(comb_mod(K-1,i-1,mod)*comb_mod(N-K+1,i,mod)%mod)
    return ans
print(*solve(),sep='\n')

### FIXED CODE ###

def solve():
    mod = 10**9+7
    N, K = map(int, input().split())
    ans = []
    combs1 = [1]*K
    combs2 = [1]*(K+1)
    for i in range(1,K):
        combs1[i] = combs1[i-1]*(K-i)*pow(i,mod-2,mod)%mod
    for i in range(1,K+1):
        combs2[i] = combs2[i-1]*(N-K+2-i)*pow(i,mod-2,mod)%mod
    for i in range(1,K+1):
        ans.append(combs1[i-1]*combs2[i]%mod)
    return ans
print(*solve(),sep='\n')
### BUGGY CODE ###

k,s = map(int,input().split())
if 3*k==s:
  print(1)
else:
  list = [ x + y + z for x in range(k+1) for y in range(k+1) for z in range(k+1)] 
  print(list.count(s))

### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

# ARC060C - 高橋君とカード / Tak and Cards (ABC044C)
from itertools import combinations


def ans(i, A, lst):
    comb = tuple(combinations(lst, i))
    return sum(1 for i in comb if sum(i) == A)


def main():
    n, a = list(map(int, input().rstrip().split()))
    lst = tuple(map(int, input().rstrip().split()))
    cnt = 0
    for i in range(1, n + 1):
        cnt += ans(i, i * a, lst)
    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
def main():
    N, A = tuple(map(int, input().rstrip().split()))
    X = tuple(map(int, input().rstrip().split()))
    x = max(X)
    # dp[i][j][k] := patterns to make k by j cards from X1, X2, ..., Xi
    dp = [[[0] * (N * 50 + 1) for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(N):
            for k in range(N * 50 + 1):
                if dp[i][j][k]:
                    dp[i + 1][j][k] += dp[i][j][k]
                    dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]
    ans = sum(dp[N][i][i * A] for i in range(1, N + 1))
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
I = list(map(int, input().split()))
minX = 10000000000
end = I.pop() 
for i in range(len(I)):
  minX = min(minX, abs(sum(I) - end ) )
  end += I.pop() 
  
print(minX)

### FIXED CODE ###

N = int(input())
I = list(map(int, input().split()))
minX = 10000000000
end = I.pop()
sumI = sum(I)
for i in range(len(I)):
  minX = min(minX, abs(sumI - end ) )
  popped = I.pop()
  sumI -= popped
  end += popped
  
print(minX)
### BUGGY CODE ###

#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    W = W+2
    c = [["@"]*W]
    for i in range(H):
        c.append(["@"]+list(input())+["@"])
    c.append(["@"]*W)
    H = H+2

    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    # ヒープでなくて良い。
    # 高々1しか加わっていかないため、キューに加えられた順で十分昇順になる。
    Q = [(0, x1, y1, 0)]
    Q += [(0, x1, y1, 1)]
    Q += [(0, x1, y1, 2)]
    Q += [(0, x1, y1, 3)]
    i = 0
    while i < len(Q):
        curr, x, y, DXY = Q[i]
        c[x][y] = "@"
        dx, dy = DX[DXY], DY[DXY]
        for k in range(1, K+1):
            X, Y = x+k*dx, y+k*dy
            if c[X][Y] == "@":
                break
            if 0 < dist[X][Y] < curr+1:
                break
            # if dist[X][Y] == curr+1:
            #     continue
            dist[X][Y] = curr+1
            Q.append((curr+1, X, Y, (DXY+1) % 4))
            Q.append((curr+1, X, Y, (DXY-1) % 4))
        else:
            Q.append((curr+1, X, Y, DXY))
        if 0 < dist[x2][y2]:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()