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

from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


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


while q:
  cur=q.popleft()

  if 0<=cur[0]+1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]+1][cur[1]]==-1:
      lis[cur[0]+1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]+1,cur[1]))
  
  if 0<=cur[0]-1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]-1][cur[1]]==-1:
      lis[cur[0]-1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]-1,cur[1]))

  
  if 0<=cur[0]<=h-1 and 0<=cur[1]+1<=w-1:
    if lis[cur[0]][cur[1]+1]==-1:
      lis[cur[0]][cur[1]+1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]+1))
      
  if 0<=cur[0]<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[cur[0]][cur[1]-1]==-1:
      lis[cur[0]][cur[1]-1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]-1))      
  
print(max(max(l) for l in lis))



### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


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


while q:
  cur=q.popleft()
  i,j=cur[0],cur[1]

  if 0<=i+1<=h-1 and 0<=j<=w-1:
    if lis[i+1][j]==-1:
      lis[i+1][j]=lis[i][j]+1
      q.append((i+1,j))
  
  if 0<=i-1<=h-1 and 0<=j<=w-1:
    if lis[i-1][j]==-1:
      lis[i-1][j]=lis[i][j]+1
      q.append((i-1,j))

  
  if 0<=i<=h-1 and 0<=j+1<=w-1:
    if lis[i][j+1]==-1:
      lis[i][j+1]=lis[i][j]+1
      q.append((i,j+1))
      
  if 0<=i<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[i][j-1]==-1:
      lis[i][j-1]=lis[i][j]+1
      q.append((i,j-1))      
  
print(max(max(l) for l in lis))
### BUGGY CODE ###

# 1,0,-1
# K枚
A, B, C, K = map(int, input().split())

ans = 0
while(K!=0):
    if A!=0:
        ans += 1
        A -= 1
        K -= 1
    elif B!=0:
        ans += 0
        B -= 1
        K -= 1
    elif C!=0:
        ans += -1
        C -= 1
        K -= 1

print(ans)

### FIXED CODE ###

# 1,0,-1
# K枚
A, B, C, K = map(int, input().split())

ans = 0
while(K!=0):
    #print(A, B, C, K, ans)
    
    if A!=0:
        if A <= K:
            ans += A*1
            K -= A
            A = 0
        else:
            ans += K*1
            A -= K
            K = 0
    elif B!=0:
        if B <= K:
            ans += B*0
            K -= B
            B = 0
        else:
            ans += K*0
            B -= K
            K = 0
    elif C!=0:
        if C <= K:
            ans += C*-1
            K -= C
            C = 0
        else:
            ans += K*-1
            C -= K
            K = 0

    if A==0 and B==0 and C==0:
        break
print(ans)
### BUGGY CODE ###

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1
for p in Ps:
    g = lcm(g,p)

print(sum([g // p for p in Ps]) % (10 ** 9 + 7))



### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1
for p in Ps:
    g = lcm(g,p)
ans = 0

print(sum([g // p for p in Ps]) % (10 ** 9 + 7))
### BUGGY CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    a_arr = [None]
    for i in range(N):
        _ = int(_in[i+1])  # type:int
        a_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    memo = []
    now = 1
    cnt = 0
    while True:
        cnt += 1
        _ = a_arr[now]
        if _ in memo:
            cnt = -1
            break
        elif _ == 2:
            break
        else:
            memo.append(_)
            now = _
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    a_arr = [None]
    for i in range(N):
        _ = int(_in[i+1])  # type:int
        a_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    memo = []
    now = 1
    for i in range(N):
        _ = a_arr[now]
        if _ == 2:
            cnt = i+1
            break
        else:
            now = _
    else:
        cnt = -1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [int_list.count(i) for i in range(1, N+1)]

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2

# tmp_ans = sum([cnt_list[i]*(cnt_list[i]-1) // 2 for i in range(N) if cnt_list[i] > 1])

for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])

# ret_list = [0 if cnt_list[i] < 1 else tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2 for i in range(N)]

# [print(ret_list[i-1]) for i in int_list]

### FIXED CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [0] * N

for i in int_list:
    cnt_list[i-1] += 1

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2


for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])
### BUGGY CODE ###

INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


def main():
    M = int(input())
    digits = []
    S = 0

    for i in range(M):
        d, c = list(map(int, input().split()))

        if d == 0 and i == 0:
            continue

        for i in range(c):
            digits.append(d)
            S += d

    print((len(digits) - 1) + (S - 1) // 9)


if __name__ == '__main__':
    main()


### FIXED CODE ###

INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


def main():
    M = int(input())
    N = 0
    S = 0

    for i in range(M):
        d, c = list(map(int, input().split()))

        if d == 0 and i == 0:
            continue

        S += d * c
        N += c

    print((N - 1) + (S - 1) // 9)


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

n,q=map(int,input().split())
s=input()
L=[]
for i in range(q):
    a,b=map(int,input().split())
    L.append(s[a-1:b])
for i in L:
      ans=0
      for j in range(len(i)-1):
            if "AC"==i[j:j+2]:
                  ans+=1
      print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
L=[list(map(int,input().split())) for i in range(q)]

L2=[0]
r=0
for i in range(1,n):
      if s[i-1]+s[i]=="AC":
            r+=1
      L2.append(r)

for i in range(q):
      print(L2[L[i][1]-1]-L2[L[i][0]-1])
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]

d = [num for num in range(1, n + 1)]
for i in range(m):
    if h[ab[i][0] - 1] > h[ab[i][1] - 1]:
        if ab[i][1] in d:
            d.remove(ab[i][1])
    elif h[ab[i][0] - 1] < h[ab[i][1] - 1]:
        if ab[i][0] in d:
            d.remove(ab[i][0])
    elif h[ab[i][0] - 1] == h[ab[i][1] - 1]:
        if ab[i][1] in d:
            d.remove(ab[i][1])
        if ab[i][0] in d:
            d.remove(ab[i][0])

print(len(d))

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]

d = {num for num in range(1, n + 1)}
for i in range(m):
    if h[ab[i][0] - 1] > h[ab[i][1] - 1]:
        d.discard(ab[i][1])
    elif h[ab[i][0] - 1] < h[ab[i][1] - 1]:
        d.discard(ab[i][0])
    elif h[ab[i][0] - 1] == h[ab[i][1] - 1]:
        d.discard(ab[i][1])
        d.discard(ab[i][0])

print(len(d))
### BUGGY CODE ###

k=int(input())

import math
 
res=0
 
for n in range(1,k+1):
    for i in range(1,k+1):
        for j in range(1,k+1):

            res+=math.gcd(math.gcd(n,i),j)

print(res)

### FIXED CODE ###

k=int(input())

from math import gcd
 
res=0
 
for n in range(1,k+1):
    for i in range(1,k+1):
        for j in range(1,k+1):

            res+=gcd(gcd(n,i),j)

print(res)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
BCs = [(b,a*b) for a,b in zip(sorted(list(map(int, input().split()))), sorted(list(map(int, input().split())))[::-1])]

def f(target):
    return sum([math.ceil(max(0, c - target)/b)for b, c in BCs])<=K

if __name__ == '__main__':
    min_i, max_i, index = 0, 10**12, 1
    while True:
        index, max_i, min_i = ((index-1 + min_i)//2, index-1, min_i) if f(index) else ((index+1 + max_i)//2, max_i, index+1)
        if min_i > max_i:
            print(min_i)
            break

### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

import sys
input=sys.stdin.readline

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
maze=[list(input()) for _ in range(h)]

sy-=1
sx-=1
gy-=1
gx-=1

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

from collections import deque

dis[sy][sx]=0

def pri(x):
    for item in x:
        print(item)

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        maze[gy][gx]="G"

        #pri(dis)
        #pri(maze)

        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    d.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break

print(-1)
    


                










### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

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

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

from math import factorial
def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return factorial(n)//(factorial(2)*factorial(n-2))

c=[a.count(i) for i in range(1,n+1)]
d=[comb(m) for m in c]

for i in range(n):
    num=d[a[i]-1]
    d[a[i]-1]=comb(c[a[i]-1]-1)
    print(sum(d))
    d[a[i]-1]=num

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return (n*(n-1))//2

from collections import Counter
c=Counter(a)
# print(c)
d={i:comb(j) for i,j in c.items()}
# print(d)
s=sum(d.values())
# print(s)

for i in a:
    print(s-d[i]+comb(c[i]-1))
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    l = 1
    for a in A:
        l = gm(l, a)

    res = 0
    for a in A:
        res = (res + l // a) % mod
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

n, w = map(int, input().split())

value = []
weight = []
num = []

for _ in range(n):
  vi, wi, ni = map(int, input().split())
  value.append(vi)
  weight.append(wi)
  num.append(ni)

def to_digit(x):
  acc = 1
  ret = [0]
  while x >= acc:
    ret.append(acc)
    x -= acc
    acc *= 2
  if x:
    ret.append(x)
  return ret

num = list(map(to_digit, num))

dp = [0 for _ in range(w + 1)]
for i in range(n):
  vi = value[i]
  wi = weight[i]
  numsi = num[i]
  for k in numsi:
    for j in range(w, -1, -1):
      if j >= wi * k:
        dp[j] = max(dp[j], dp[j - wi * k] + vi * k)

print(dp[w])


### FIXED CODE ###

def main():
  n, w = map(int, input().split())
  
  value = []
  weight = []
  num = []
  
  for _ in range(n):
    vi, wi, ni = map(int, input().split())
    value.append(vi)
    weight.append(wi)
    num.append(ni)
  
  def summary(x):
    acc = 1
    ret = [0]
    while x >= acc:
      ret.append(acc)
      x -= acc
      acc *= 2
    if x:
      ret.append(x)
    return ret
  
  num = list(map(summary, num))
  
  dp = [0 for _ in range(w + 1)]
  for i in range(n):
    vi = value[i]
    wi = weight[i]
    numsi = num[i]
    for k in numsi:
      wik = wi * k
      vik = vi * k
      for j in range(w, wik - 1, -1):
        pre = dp[j - wik] + vik
        if dp[j] < pre:
          dp[j] = pre
  
  print(dp[w])

main()
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D
#?°´??????????????¢????¨????
import re

def cal_puddle(puddle_list):
    depth = 0
    score = 0
    for symbol in puddle_list:
        if symbol == "\\":
            score += depth + 0.5
            depth += 1
        if symbol == "/":
            depth -= 1
            score += depth + 0.5
        if symbol == "_":
            score += depth
            
    return int(score)

def get_puddle_index(diagram_list):

    depth = 0
    for i, symbol in enumerate(diagram_list):
        if symbol == "\\":
            depth += 1
        elif symbol == "/":
            depth = depth - 1

        if depth == 0:
            return i

    return False

def cal(diagram):
    puddle_areas = []
    diagram_list = []

    puddle_list = []
    i = 0
    while i < len(diagram):
        if diagram[i] == "\\":
            puddle_end = get_puddle_index(diagram[i:])
            if puddle_end:
                puddle_areas.append(cal_puddle(diagram[i: i + puddle_end + 1]))
                i = i + puddle_end
        i += 1

    for puddle in puddle_list:
        puddle_areas.append(cal_puddle(puddle))
        
    return puddle_areas

        
if __name__ == "__main__":
    a = input()
    result = cal(a)
    print(sum(result))
    print(str(len(result)) + "".join([" " + str(a) for a in result]))

### FIXED CODE ###

def cal_puddle(puddle):
    depth = 0
    score = 0
    for s in puddle:
        if s == "\\":
            score += depth + 0.5
            depth += 1
        elif s == "/":
            depth -= 1
            score += depth + 0.5
        elif s == "_":
            score += depth

        if depth == 0:
            return int(score)
    return int(score)

def get_puddles(diagram):
    hight = 0
    top_list = []
    in_puddle = True
    for index, s in enumerate(diagram + "\\"):
        if s == "/":
            in_puddle = True
            hight += 1
        if s == "\\":
            if in_puddle:
                in_puddle = False
                top_list.append([hight, index])
            hight -= 1

    puddles = []
    prev_hight = 0
    hight_list = [h for h, i in top_list]
    i = 0
    while i < len(top_list) - 1:
        cur_top = top_list[i]
        next_tops = list(filter(lambda top:cur_top[0] <= top[0], top_list[i + 1:]))
        #print(next_tops)
        if next_tops:
            next_top = next_tops[0]
            puddles.append((cur_top[1], next_top[1]))
            i = top_list.index(next_top)
        else:
            cur_top[0] -= 1
            cur_top[1] += diagram[cur_top[1] + 1:].index("\\") + 1
    #print(hight_list)
    #print(top_list)
    #print(puddles)
    return puddles

def main():
    diagram = input()
    result = []
    for s,e in get_puddles(diagram):
        result.append(cal_puddle(diagram[s:e]))
    print(sum(result))
    print(str(len(result)) + "".join([" " + str(i) for i in result]))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
mod = 2019
rem = [0] * mod
rem[0] = 1
now = 0
for k,v in enumerate(S[::-1]):
  now += int(v) * (10 ** k)
  rem[now % mod] += 1
ans = 0
for i in rem:
  ans += i * (i-1) // 2
print(ans)

### FIXED CODE ###

S = input()
mod = 2019
rem = [0] * mod
rem[0] = 1
now = 0
for k,v in enumerate(S[::-1]):
  now += int(v) * pow(10,k,mod)
  rem[now % mod] += 1
ans = 0
for i in rem:
  ans += i * (i-1) // 2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    a = 0
    a_n = [a]
    for a_i in A:
        a += a_i
        a_n.append(a)

    b = 0
    b_n = [b]
    for b_i in B:
        b += b_i
        b_n.append(b)
    b_n = b_n[::-1]

    max_ = 0
    max_j = M
    for i, a in enumerate(a_n):
        for j, b in enumerate(b_n[-(max_j+1):]):
            if b <= (K-a):
                num = i+max_j-j
                if max_ < num:
                    max_ = num
                max_j -= j
                break

    return max_


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    print(solve(N, M, K, A, B))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    a = 0
    a_n = [a]
    for a_i in A:
        a += a_i
        a_n.append(a)

    b = 0
    b_n = [b]
    for b_i in B:
        b += b_i
        b_n.append(b)

    ans = 0
    j = M
    for i, a in enumerate(a_n):
        if a > K:
            break
        while b_n[j] > (K-a):
            j -= 1
        ans = max(ans, i+j)

    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    print(solve(N, M, K, A, B))

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

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a,f=~w+a*w+b,~w+f*w+g
d[a]=1
q=[a]
for s in q:
 if s==f:break
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   q+=t,;d[t]=d[s]+1
print(d[f]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)