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

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*h for _ in range(w))
    d=tuple([0]*h for _ in range(w))
    for t,x,y in zip(s,a,b):
        for i,u in enumerate(t[:-1]):
            x[i]=x[i-1]+1if u=='.'else 0
        for i,u in enumerate(t[-2::-1]):
            y[~i]=y[-i]+1if u=='.'else 0
    for t,x,y in zip(zip(*s),c,d):
        for i,u in enumerate(t):
            x[i]=x[i-1]+1if u=='.'else 0
        for i,u in enumerate(t[::-1]):
            y[~i]=y[-i]+1if u=='.'else 0
    print(max(sum(u)-3for t in zip(a,b,zip(*c),zip(*d))for u in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = (lcm * T[i]) // gcd(lcm, T[i])
for i in range(N):
  ans = (ans + lcm // T[i]) % MOD
print(ans)

### FIXED CODE ###

import fractions
N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = lcm * T[i] // fractions.gcd(lcm, T[i])
for x in T:
  ans += lcm // x
print(ans % MOD)
### BUGGY CODE ###

import sys
import heapq
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):a,b=o();e[a]+=[(b,1)];e[b]+=[(a,1)]
k=int(raw_input())
for _ in range(k):v,p=o();e[v]+=[(0,p)];e[0]+=[(v,p)]
vis=[False]*(n+1)
cost=[0]*(n+1)
q=[(0,0)]
heapq.heapify(q)
while len(q):
    c,v=heapq.heappop(q)
    vis[v]=True
    cost[v]=c
    for (w,d) in e[v]:
        if not vis[w]:heapq.heappush(q,(c+d,w))
for i in range(1,n+1):
    for w,d in e[i]:
        if w!=0 and abs(cost[i]-cost[w])!=1:print 'No';sys.exit()
print 'Yes'
for i in range(n):print cost[i+1]


### FIXED CODE ###

import sys
import heapq
o=lambda:map(int,raw_input().split())
n=int(raw_input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):a,b=o();e[a]+=[(b,1)];e[b]+=[(a,1)]
k=int(raw_input())
for _ in range(k):v,p=o();e[v]+=[(0,p)];e[0]+=[(v,p)]
vis=[False]*(n+1)
cost=[10**9]*(n+1)
q=[(0,0)]
heapq.heapify(q)
while len(q):
    c,v=heapq.heappop(q)
    vis[v]=True
    cost[v]=c
    for (w,d) in e[v]:
        if not vis[w] and c+d<cost[w]:
            heapq.heappush(q,(c+d,w))
            cost[w]=c+d
for i in range(1,n+1):
    for w,d in e[i]:
        if w!=0 and abs(cost[i]-cost[w])!=1:print 'No';sys.exit()
print 'Yes'
for i in range(n):print cost[i+1]
### BUGGY CODE ###

# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

edge = [[] for _ in range(n)]
cost = {}

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    cost[(a,b)] = -c

d = [inf for _ in range(n)]
d[0] = 0
cnt = 0
while cnt<n:
    update = False
    for fi in range(n):
        for ti in edge[fi]:
            if d[fi]!=inf and d[ti]>d[fi]+cost[(fi,ti)]:
                d[ti] = d[fi]+cost[(fi,ti)]
                update = True
    if not update:
        break
    cnt += 1
ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    for fi in range(n):
        for ti in edge[fi]:
            if d[fi]!=inf and d[ti]>d[fi]+cost[(fi,ti)]:
                d[ti] = d[fi]+cost[(fi,ti)]
                negative[ti] = True
            if negative[fi] == True:
                negative[ti] = True
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

ea = []
eb = []
cost = []

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    ea.append(a)
    eb.append(b)
    cost.append(-c)

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            update = True
    if not update:
        break

ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            if not negative[b]:
                update = True
            negative[b] = True
        if negative[a] and not negative[b]:
            negative[b] = True
            update = True
    if not update:
        break
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)
### BUGGY CODE ###

import random

data = list(map(int, input().split()))
lst = data[:]
n = 0
minimum = 1000000

for i in range(1000):
    while True:
        if data[0] == data[1] and data[1] == data[2]:
            data = lst[:]
            if n < minimum:
                minimum = n
            n = 0
            break

        f = random.randint(0, 1)
        if f == 0:
            lst[random.randint(0, 2)] += 1
            lst[random.randint(0, 2)] += 1
        else:
            lst[random.randint(0, 2)] += 2
        n += 1

print(minimum)


### FIXED CODE ###

a, b, c = map(int, input().split())

m = max(a, b, c)
if 3*m%2 == (a+b+c)%2:
    print((3*m-(a+b+c))//2)
else:
    print((3*(m+1)-(a+b+c))//2)
### BUGGY CODE ###

from sys import stdin

n = stdin.readline().rstrip().split()
a = stdin.readline().rstrip().split()

total = 1
for i in a:
    total = total*int(i)

if(total > 1000000000000000000): total = -1
print(total)

### FIXED CODE ###

from sys import stdin
import sys

n = stdin.readline().rstrip().split()
a = stdin.readline().rstrip().split()

if '0' in a:
    print(0)
    sys.exit()

total = 1
for i in a:
    total = total*int(i)

    if(total > 1000000000000000000):
        print(-1)
        sys.exit()

print(total)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))

count = 1

for i in range(1,n):
    temp = p[:i]
    if min(temp) >= p[i]:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))

count = 0
m = p[0]

for i in range(0,n):
    if m >= p[i]:
        count += 1
    m = min(m, p[i])

print(count)
### BUGGY CODE ###

import bisect

if __name__ == '__main__':
    n = int(input())
    s = list(input())
    r = []
    g = []
    b = []

    for i in range(n):
        if s[i] == "R":
            r.append(i)
        elif s[i] == "G":
            g.append(i)
        else:
            b.append(i)
    x = len(b)
    ans = 0
    for i in range(n):
        for j in range(i, n):
            if s[i] == s[j]:
                continue
            if s[i] == "R" and s[j] == "G":
                out = j * 2 - i
                tmp = bisect.bisect_left(b, j)
                t = len(b) - tmp
                ans += (t - 1) if out in b[tmp:] else t

            elif s[i] == "R" and s[j] == "B":
                out = j * 2 - i
                tmp = bisect.bisect_left(g, j)
                t = len(g) - tmp
                ans += (t - 1) if out in g[tmp:] else t

            elif s[i] == "G" and s[j] == "B":
                out = j * 2 - i
                tmp = bisect.bisect_left(r, j)
                t = len(r) - tmp
                ans += (t - 1) if out in r[tmp:] else t

            elif s[i] == "G" and s[j] == "R":
                out = j * 2 - i
                tmp = bisect.bisect_left(b, j)
                t = len(b) - tmp
                ans += (t - 1) if out in b[tmp:] else t

            elif s[i] == "B" and s[j] == "R":
                out = j * 2 - i
                tmp = bisect.bisect_left(g, j)
                t = len(g) - tmp
                ans += (t - 1) if out in g[tmp:] else t

            elif s[i] == "B" and s[j] == "G":
                out = j * 2 - i
                tmp = bisect.bisect_left(r, j)
                t = len(r) - tmp
                ans += (t - 1) if out in r[tmp:] else t

    print(ans)


### FIXED CODE ###

import sys

if __name__ == '__main__':
    input = sys.stdin.readline
    n = int(input())
    s = list(input())
    s.remove('\n')
    r = 0
    g = 0
    b = 0
    for i in s:
        if i == "R":
            r += 1
        elif i == "G":
            g += 1
        else:
            b += 1
    ans = r * g * b
    for i in range(n):
        for j in range(i, n):
            out = j * 2 - i
            if out >= n:
                continue
            if len({s[i], s[j], s[out]}) == 3:
                ans -= 1
    print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())

R = min(R, L+2019*2) # 長さを制限しても同じ
MOD = 2019
ans = 2018

for i in range(L, R): # iはLからR-1まで
    for j in range(i+1, R+1): # jはi+1からRまで
        n = i*j%MOD
        ans = min(n, ans)

print(ans)



### FIXED CODE ###

L, R = map(int, input().split())

R = min(R, L+(2019)) # 長さを制限しても同じ
MOD = 2019
ans = 2018

for i in range(L, R): # iはLからR-1まで
    for j in range(i+1, R+1): # jはi+1からRまで
        n = (i*j)%MOD
        ans = min(n, ans)

print(ans)
### BUGGY CODE ###

def get_exp_mod(base, exp, mod):
    exp_bin = str(format(exp, 'b'))  # ２進表現
    res = 1
    for i in range(len(exp_bin)):
        if exp_bin[-i - 1] == '1':
            res = res * base % mod
        base = base * base % mod  # base^2^nをmodで割ったあまり

    return res


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

## TODO:0の時

# 2^n -1のmodを求める
all_case = (get_exp_mod(2, n, mod) - 1) % mod
#print(all_case)

# nCa modを求める
case_a = 1
for i in range(a):
    case_a = case_a * (n - i) % mod
    case_a = case_a * get_exp_mod(i+1, mod-2, mod) % mod
#print(case_a)

case_b = 1
for i in range(b):
    case_b = case_b * (n - i) % mod
    case_b = case_b * get_exp_mod(i+1, mod-2, mod) % mod
#print(case_b)

print((all_case - case_a - case_b) % mod)


### FIXED CODE ###

def get_exp_mod(base, exp, mod):
    exp_bin = str(format(exp, 'b'))  # ２進表現
    res = 1
    for i in range(len(exp_bin)):
        if exp_bin[-i - 1] == '1':
            res = res * base % mod
        base = base * base % mod  # base^2^nをmodで割ったあまり

    return res


def comb(n, r, mod):
    X = 1
    Y = 1
    for i in range(r):
        X = X * (n - i) % mod
        Y = Y * (i + 1) % mod
    return X * get_exp_mod(Y, mod - 2, mod) % mod


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


# 2^n -1のmodを求める
all_case = (get_exp_mod(2, n, mod) - 1) % mod

# nCa modを引く
print((all_case - comb(n, a, mod) - comb(n, b, mod)) % mod)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2*j - i
        if j < k < n and s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            cnt += 1
print(s.count('R') * s.count('G') * s.count('B') - cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
    for j in range(i + 1, n):
        k = 2*j - i
        if j < k < n and len({s[i], s[j], s[k]}) == 3:
            cnt -= 1
print(cnt)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
card = list(map(int, input().split()))
data = []
for i in range(m):
    data.append(list(map(int, input().split())))
data.sort(key=lambda x:x[1])
data.reverse()
card.sort()
total = 0
k = 0

for i in range(m):
    for j in range(min(data[i][0] ,len(card))):
        if card[j] < data[i][1]:
            card[j] = data[i][1]
            k = j
        else:
            k = j - 1
            break
    total += sum(card[:k + 1])
    card = card[k+1:]
total += sum(card)
print(total)

### FIXED CODE ###

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
count = 0
pre_index = 0
#print(data)
#print(a)
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    count = min(data[i][0], insert_index - pre_index)
    for j in range(pre_index, pre_index + count):
        if j >= n:
            break
        a[j] = 0
    ans += count * data[i][1]
    pre_index = pre_index + count
print(ans + sum(a))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
cnt = 0
visited[f] = True
flg = True
while True:
    t = a[f]
    if visited[t]:
        flg = False
        break
    else:
        cnt += 1
        if t == 1:
            break
        f = t
print(cnt) if flg else print(-1)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
visited[f] = True
cnt = 0
while True:
    cnt += 1
    t = a[f]
    if t == 1:
        flg = True
        break
    if visited[t]:
        flg = False
        break
    visited[t] = True
    f = t
print(cnt) if flg else print(-1)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
if 1 in A:
    B=[1]+[0]*N
else:
    B=[1]+[1]+[0]*(N-1)
i=2
while i<=N:
    if i not in A:
        B[i] = (B[i - 1] + B[i - 2]) % (10 ** 9 + 7)
    i+=1
print(B[N])

### FIXED CODE ###

N,M=map(int,input().split())
B=[1]+[1]+[0]*(N-1)
for j in range(M):
    a=int(input())
    B[a]=-1
    if a==1:
        B[a]=0
i=2
while i<=N:
    if B[i]==-1:
        B[i]=0
    else:
        B[i] = (B[i - 1] + B[i - 2]) % (10 ** 9 + 7)
    i+=1
print(B[N])
### BUGGY CODE ###

input_line=input().split(" ")
N,K=int(input_line[0]),int(input_line[1])
P=input().split(" ")

for i in range(N):
    P[i]=int(P[i])

new_total_box=[]
for j in range(N-K+1):
    total=0
    for i in range(j,K+j):
        total=total+P[i]+1
    new_total_box.append(total)
    
max_value = max(new_total_box)


sol=max_value/2
    
print(sol)
    

### FIXED CODE ###

input_line=input().split(" ")
N,K=int(input_line[0]),int(input_line[1])
P=input().split(" ")
cumsum=[0]
tol=0
for i in range(N):
    P[i]=(int(P[i])+1)/2
    tol=tol+P[i]
    cumsum.append(tol)
    
k_sum=[]

for i in range(N-K+1):
  k_sum.append(cumsum[i+K]-cumsum[i])  

ans=max(k_sum)
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    tree = [[] for _ in range(n)]
    for _ in range(m):
        x, y, _ = map(int, input().split())
        tree[x - 1].append(y - 1)
        tree[y - 1].append(x - 1)

    def dfs(v):
        for u in tree[v]:
            if visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u)

    visited = [False for _ in range(n)]
    res = 0
    for i in range(n):
        if not visited[i]:
            res += 1
            visited[i] = True
            dfs(i)

    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

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

tree = [[] for _ in range(n)]
for _ in range(m):
    x, y, z = map(int, input().split())
    tree[x - 1].append(y - 1)
    tree[y - 1].append(x - 1)

visited = [False for _ in range(n)]


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        elif visited[u]:
            continue
        else:
            visited[u] = True
            dfs(u, v)


res = 0
for i in range(n):
    if not visited[i]:
        visited[i] = True
        dfs(i, -1)
        res += 1

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

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst=lst+[[int(s) for s in input().split()]]
lst.sort()
n=0
i=0
cost=0
while(n<M):
  n+=lst[i][1]
  cost+=lst[i][0]*lst[i][1]
  i+=1
if(n>M):
  cost-=lst[i-1][0]*(n-M)
print(cost)

### FIXED CODE ###

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

max_k_list = [0] * (K ** 2)
i = 0
for a_i in range(X):
    for b_i in range(Y):
        for c_i in range(Z):
            if (a_i + 1) * (b_i + 1) * (c_i + 1) <= K:
                max_k_list[i] = a_list[a_i] + b_list[b_i] + c_list[c_i]
                i += 1

max_k_list.sort(reverse = True)
[print(k) for k in max_k_list[:K]]


### FIXED CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

heap = []
heapq.heappush(heap, (-(a_list[0] + b_list[0] + c_list[0]), 0, 0, 0))
searched = []
result = [0] * K

for k in range(K):
    elem = heapq.heappop(heap)
    result[k] = - elem[0]

    if elem[1] + 1 <= X - 1:
        a_next = (-(a_list[elem[1] + 1] + b_list[elem[2]] + c_list[elem[3]]), elem[1] + 1, elem[2], elem[3])
        if not a_next in searched:
            heapq.heappush(heap, a_next)
            searched.append(a_next)

    if elem[2] + 1 <= Y - 1:
        b_next = (-(a_list[elem[1]] + b_list[elem[2] + 1] + c_list[elem[3]]), elem[1], elem[2] + 1, elem[3])
        if not b_next in searched:
            heapq.heappush(heap, b_next)
            searched.append(b_next)

    if elem[3] + 1 <= Z - 1:
        c_next = (-(a_list[elem[1]] + b_list[elem[2]] + c_list[elem[3] + 1]), elem[1], elem[2], elem[3] + 1)
        if not c_next in searched:
            heapq.heappush(heap, c_next)
            searched.append(c_next)

[print(k) for k in result]
### BUGGY CODE ###

S = input()
N = len(S)
amari = [0 for i in range(2019)]
for i in range(N):
    amari[int(S[i : N]) % 2019] += 1
ans = amari[0]
for i in amari:
    if i > 1:
       ans += i * (i - 1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
N = len(S)
amari = [0 for i in range(2019)]
before = int(S[0])
amari[before] += 1
S = S[1::]
keta = 1
for i in S:
    i = int(i)
    keta = (keta * 10) % 2019
    x = (keta * i + before) % 2019
    amari[x] += 1
    before = x
ans = amari[0]
for i in amari:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
for f in range(k):
    a1=list(range(n+1))
    a1=[0 for s in a1]
    for x in range(n):
        y=x-a[x]
        if y<0:
            y=0
        a1[y]=a1[y]+1    
        z=x+a[x]
        if z>n-1:
            z=n-1
        a1[z+1]=a1[z+1]-1
    for x in range(n):    
        a[x]=sum(a1[:x+1])
    if sum(a)==n**2:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

N = int(input())
S = input()

ans = 3*10^5

for i in range(N):
    n = 0
    for j in range(i):
        if "W" == S[j]:
            n += 1
    for j in range(i+1, N):
        if "E" == S[j]:
            n += 1

    if ans > n:
        ans = n

print(ans)


### FIXED CODE ###

N = int(input())
S = input()

n = p = S[1:].count("E")

for i in range(0,N-1):
    if S[i+1] == "E":
        p -= 1
    if S[i] == "W":
        p += 1
    n = min(p, n)

print(n)
### BUGGY CODE ###

n = int(input())

x = 1
for i in range(1,n+1):
    x = x*i

print(x%(10**9+7))


### FIXED CODE ###

n = int(input())
inf =1000000007

x = 1
for i in range(1,n+1):
    x = x*i%inf

print(x)
### BUGGY CODE ###

from collections import deque
H,W,K = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1
Pond = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)
#print(Pond)
Q = deque([])
Q.append((sx,sy))
reach = [[INF]*W for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  nx,ny = Q.popleft()
  step = K
  for i in range(4):
    for fac in range(1,K+1):
      tx = nx + fac*dxdy[i][0]
      ty = ny + fac*dxdy[i][1]
      #print(i,tx,ty)
      if 0>tx or tx>=H or 0>ty or ty>=W or Pond[tx][ty] == "@": #or reach[tx][ty] != INF:
        #print(i,tx,ty,reach[2][0])
        break #範囲外やハスがあった、到達済みの場合には終了
      #print(i,tx,ty)
      if reach[nx][ny] + 1 > reach[tx][ty]: #もし現時点よりもステップが大きい場合はだめ。
        #同じ場合は向き的に得している場合もあるので残す。
        break
      reach[tx][ty] = reach[nx][ny] + 1
      Q.append((tx,ty))
      if tx == gx and ty == gy:
        print(reach[gx][gy])
        exit()
#print(reach)
ans = reach[gx][gy]
if ans == INF:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      if reach[x][y]+1 < reach[nx][ny]:
        reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
        Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)
### BUGGY CODE ###

def all_sum(val):
    sum = 0
    for i in range(val):
        sum = sum + i + 1
    return sum / val


[n, k] = input().split()

p = input().split()

k = int(k)
n = int(n)
p = [int(i) for i in p]

total = 0
max_total = 0
for i in range(k):
    total = total + p[i]
max_total = total
max_ind = 0

for i in range(n - k):
    total = total - p[i] + p[i + k]
    if(max_total < total):
        max_total = total
        max_ind = i + 1
ans = 0
for i in range(k):
    ans = ans + all_sum(p[i + max_ind])

print("{:.8f}".format(ans))


### FIXED CODE ###

def all_sum(val):
    sum = 0
    for i in range(val):
        sum = sum + i + 1
    return sum / val


[n, k] = input().split()

p = input().split()

k = int(k)
n = int(n)
p = [int(i) for i in p]

total = 0
max_total = 0
for i in range(k):
    total = total + p[i]
max_total = total
max_ind = 0

for i in range(n - k):
    total = total - p[i] + p[i + k]
    if(max_total < total):
        max_total = total
        max_ind = i + 1
ans = 0
for i in range(k):
    ans = ans + all_sum(p[i + max_ind])

print("{:.8f}".format(ans))