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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def check(num):
    num = list(str(num))
    res = 0
    for a,b,c,d in abcd:
        if int(num[b-1]) - int(num[a-1]) == c:
            res += d
    return res

n,m,q = LI()
abcd = [LI() for _ in range(q)]
que = deque()
que.append(1)
ans = 0
f = defaultdict(int)
while que:
    fig = que.popleft()
    if len(str(fig)) <= n+1:
        num = int(str(fig)[-1])
        for i in range(num, m+1):
            que.append(int(str(fig)+str(i)))
    else:
        ans = max(ans, check(fig))
print(ans)
        

    

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def check(num):
    res = 0
    for a,b,c,d in abcd:
        if num[b-1] - num[a-1] == c:
            res += d
    return res

def dfs(x, y, z, res):
    if y == n:
        res = max(res, check(x))
        return res
    for i in range(z, m+1):
        res = max(res, dfs(x + [i], y+1, i, res))
    return res

n, m, q = LI()
abcd = [LI() for _ in range(q)]
ans = dfs([1], 0, 1, 0)
print(ans)
### BUGGY CODE ###

S = input()[::-1]
S_len = len(S)  # <= 200000
ans = 0
for i in range(S_len+1):
    tmp = S[i:i+3]
    j = i + 3
    while j < S_len:
        tmp += S[j]
        if int(tmp[::-1]) % 2019 == 0:
            ans += 1
        j += 1

print(ans)


### FIXED CODE ###

S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 = (x_10 * 10) % 2019
for i in dp:
    ans += i * (i-1) // 2
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
n = int(input())
print(':',end=' ')
array = []
count = 0
while True:
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n-1:
            count += 1
            break
    if count == 15:
        break
array.append(n)
for i in range(len(array)):
    print(array[i],end=' ')
print('')

### FIXED CODE ###

# -*- coding:utf-8 -*-

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    if n == 999993031:
        break
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 24:
        break

array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')
### BUGGY CODE ###

H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
DP = []
for i in range(M):
    hh, ww = map(int, input().split())
    h[hh - 1] += 1
    w[ww - 1] += 1
    DP.append((hh - 1, ww - 1))

hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0

for i in hhhh:
    for j in wwww:
        if (i, j) not in DP:
            check = 1
            break
print(hhh + www - (1 - check))


### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
DP = set()
for i in range(M):
    hh, ww = map(int, input().split())
    h[hh - 1] += 1
    w[ww - 1] += 1
    DP.add((hh - 1, ww - 1))

hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0

for i in hhhh:
    for j in wwww:
        if (i, j) not in DP:
            print(hhh + www)
            exit()
print(hhh + www - 1)
### BUGGY CODE ###

md=1000003
q=int(input())
for _ in range(q):
    x,d,n=map(int,input().split())
    ans=1
    s=x
    for _ in range(n):
        ans=ans*s%md
        s+=d
        if s>md:
            s-=md
    print(ans%md)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

md=10**6+3
n_max = md-1
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    for _ in range(II()):
        x,d,n=MI()
        if x==0:ans=0
        elif d==0:ans=pow(x,n,md)
        else:
            invd=pow(d,md-2,md)
            x=x*invd%md
            if x+n-1>=md:ans=0
            else:
                ans=fac[x+n-1]*ifac[x-1]*pow(d,n,md)%md
        print(ans)

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

if 0 in A:
  ans = 0
  
else:
  ans = 1
  for i in range(N):
    ans *= A[i]
  
if ans > 10**18:
  ans = -1
  
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

if 0 in A:
  ans = 0
  
else:
  ans = 1
  for i in range(N):
    ans *= A[i]
    if ans > 10**18:
      ans = -1
      break

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

N, M = [int(i) for i in input().split()]
data = list()
data_dict = dict()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([p,y])
for p, y in sorted(data,key=lambda x:x[1]):
    if data_dict.get(p) is None:
        data_dict[p] = []
    data_dict[p].append(y)

def num2str(num, len_str=6):
    return "0" * (len_str - len(str(num))) + str(num)

for p, y in data:
    rank = data_dict[p].index(y) + 1
    print(num2str(p) + num2str(rank))

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if data[j-1][1] != p:
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))
### BUGGY CODE ###

input = raw_input

x = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors

def f(x, d):
    out = (x+d) ** 5 - x ** 5
    return out

ds1 = make_divisors(x)
ds = ds1 + [-d for d in ds1]
#print("ds", ds)

found = False
for d in ds:
    if found:
        break

    b = 0
    while True:
        aa = b+d
        bb = b
        ret = f(b, d)
        #print(aa, bb, d, ret)
        
        if x == ret:
            found = True
            a = b+d
            b = b
            break
        elif ret > x:
            break
        b += 1

    if found:
        break

    b = -1
    while True:
        aa = b+d
        bb = b

        ret = f(b, d)
        #print(aa, bb, d, ret)
        
        if x == ret:
            found = True
            a = b+d
            b = b
            break
        elif ret > x:
            break
        b -= 1

assert found
print("%d %d" % (a, b))

### FIXED CODE ###

input = raw_input

x = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors

def f(x, d):
    out = (x+d) ** 5 - x ** 5
    return out

ds = make_divisors(x)
#ds = ds1 + [-d for d in ds1]
#print("ds", ds)

found = False
for d in ds:
    if found:
        break

    d0 = d
    if d0 % 2 == 0:
        b = -d0 // 2
    else:
        b = -d0 // 2 + 1

    while True:
        aa = b+d
        bb = b
        ret = f(b, d)
        #print(aa, bb, d, ret)
        
        if x == ret:
            found = True
            a = b+d
            b = b
            break
        elif ret > x:
            break
        b += 1

    if found:
        break

    #b = -1
    if d0 % 2 == 0:
        b = -d0 // 2
    else:
        b = d0 // 2 - 1

    while True:
        aa = b+d
        bb = b

        ret = f(b, d)
        #print(aa, bb, d, ret)
        
        if x == ret:
            found = True
            a = b+d
            b = b
            break
        elif ret > x:
            break
        b -= 1

    if found:
        break

    d0 = d
    d = -d
    
    if d0 % 2 == 0:
        b = d0 // 2
    else:
        b = d0 // 2 + 1

    while True:
        aa = b+d
        bb = b
        ret = f(b, d)
        #print(aa, bb, d, ret)
        
        if x == ret:
            found = True
            a = b+d
            b = b
            break
        elif ret < x:
            break
        b += 1

    if found:
        break

    if d0 % 2 == 0:
        b = d0 // 2
    else:
        b = d0 // 2 - 1
    while True:
        aa = b+d
        bb = b

        ret = f(b, d)
        #print(aa, bb, d, ret)
        
        if x == ret:
            found = True
            a = b+d
            b = b
            break
        elif ret < x:
            break
        b -= 1


assert found
print("%d %d" % (a, b))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a_sum=sum(a)
array=[]
for i in range(n-1):
    k=sum(a[0:i+1])
    array.append(k)
array_i=[]
for i in range(n-1):
    m=abs(a_sum-(2*array[i]))
    array_i.append(m)
print(min(array_i))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
v=sum(a)
x=sum(a)
ans=[]
for i in range(n-1):
    x=x-a[i]
    ans.append(abs(v-2*x))
print(min(ans))
### BUGGY CODE ###

n = int(input())
values = list(map(int, input().split()))
m = 1


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


for i in range(n):
    a = values[:]
    a.pop(i)
    g = a[0]
    for j in range(n-1):
        g = gcd(g, a[j])
    if m < g:
        m = g

print(m)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n-1):
    b = gcd(gf[i], gp[n-3-i])
    if m < b:
        m = b
if m < gf[n-2]:
    m = gf[n-2]

print(m)
### BUGGY CODE ###

def main():
    N=int(input())
    l=[0]*10**5
    A=map(int, input().split())
    for a in A:
        l[a-1]+=a
    Q=int(input())
    ans=[]
    for _ in range(Q):
        B,C=map(int, input().split())
        cnt=l[B-1]//B
        l[B-1]=0
        l[C-1]+=C*cnt
        ans.append(str(sum(l)))
    print('\n'.join(ans))
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    N=int(input())
    l=[0]*10**5
    sm=0
    A=map(int, input().split())
    for a in A:
        l[a-1]+=1
        sm+=a
    Q=int(input())
    BC=[list(map(int,input().split())) for _ in range(Q)]
    for bc in BC:
        cnt=l[bc[0]-1]
        l[bc[0]-1]=0
        l[bc[1]-1]+=cnt
        sm=sm-bc[0]*cnt+bc[1]*cnt
        print(sm)
    return

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

N,K,Q = map(int, input().split(" ")) #N:参加者 K:ポイント Q:正解数
A = [K]*N

for i in range(0,Q):
    A = list(map(lambda x:x-1,A))
    A[int(input())-1] += 1

for point in A:
    if point<=0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N,K,Q = map(int, input().split(" ")) #N:参加者 K:ポイント Q:正解数
A = [K]*N

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

for point in A:
    if point - Q <= 0 :
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)
r = A[-1]*F[0]
l = -1
while(r-l > 1):
    tmp = (l+r)//2
    k = 0
    for x, y in zip(A, F):
        if x*y > tmp:
            k += x - (tmp // y)
        #k += max(0, x - (tmp // y))
    if K >= k:
        r = tmp
    else:
        l = tmp
print(r)


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
ans=0
for i in range(n):
    if a[i] not in a[:i] and a.count(a[i])%2!=0:
        ans +=1
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()
h=a[0]
ans=1
for i in a[1:]:
    if i!=h:
        ans+=1
        h=i
    else:
        ans-=1
        h=pow(10,10)    
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
#A,B,C=map(int,input().split())
#A=list(map(int,input().split()))
T=""
whi=0
bla=0
S_=""
c1=0
for i in S:
    if i=="#":
        break
    c1+=1
for i in S:
    T=i+T
    if i==".":
        whi+=1
    else:
        bla+=1
c2=0
for i in T:
    if i==".":
        break
    c2+=1
"""
print(whi)
print(bla)
print(c1)
print(c2)
print(T)
"""
print(min(whi-c1,bla-c2))


### FIXED CODE ###

N=int(input())
S=input()
whi=0
bla=0
c1=0
dp=[[0,0] for i in range(N+1)]
for i in range(N):
    s=S[i]
    if s=="#":
        dp[i+1][0]=dp[i][0]+1
    else:
        dp[i+1][0]=dp[i][0]
for i in range(N):
    s=S[N-1-i]
    if s==".":
        dp[N-i-1][1]=dp[N-i][1]+1
    else:
        dp[N-i-1][1]=dp[N-i][1]


ans=float("inf")
for i in range(N+1):
    ans=min(ans,dp[i][0]+dp[i][1])
print(ans)
### BUGGY CODE ###

import sys
import math

def allocate(k, w):
    t = [0] * k
    avg = math.ceil(1.0 * sum(w) / k)
    while True:
        maxp = p = i = 0
        for wi in w:
            p += wi
            if p > avg:
                p -= wi
                if p > maxp:
                    maxp = p
                p = wi
                i += 1

        if p > maxp:
            maxp = p

        if i < k and maxp <= avg:
            return maxp
            
        avg += 1

if __name__ == "__main__":
    w = sys.stdin.readlines()
    k = int(w[0].split()[1])
    del w[0]
    w = [int(wi) for wi in w]
    print allocate(k, w)

### FIXED CODE ###

import sys
import math

def check(k, w, P):
    i = 0
    for t in range(k):
        p = 0
        while p + w[i] <= P:
            p += w[i]
            i += 1
            if i == len(w):
                return True
    return False

def allocate(k, w):
    t = [0] * k
    le = 0
    ri = 100000 * 10000

    while ri - le > 1:
        P = (ri + le) / 2
        if check(k, w, P):
            ri = P
        else:
            le = P
    return ri

if __name__ == "__main__":
    w = sys.stdin.readlines()
    k = int(w[0].split()[1])
    del w[0]
    w = [int(wi) for wi in w]
    print allocate(k, w)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    dp = [0 for _ in range(W+1)]
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(W-nm+1)[::-1]:
            a = nm
            if dp[j+a] < dp[j] + nv:
                dp[j+a] = dp[j] + nv
    print(max(dp))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))

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

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

ans = 10**6
for i in range(N+1):
  tmp = S[:i].count('W') + S[i+1:].count('E')
  ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

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

ans = S[1:].count('E')
tmp = S[1:].count('E')
for i in range(N-1):
  if S[i] == 'W':
    tmp += 1
  if S[i+1] == 'E':
    tmp -= 1
  ans = min(ans, tmp)
    
print(ans)
### BUGGY CODE ###

MOD = 10**9+7
def fact(n):
    dict = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

    if temp!=1:
        dict[temp] = 1

    if dict=={}:
        dict[n] = 1

    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=pow(10,9)+7
    lcma={}
    for ai in a:
      f=factorization(ai)
      for fi in f:
        if fi[0] in lcma:
          lcma[fi[0]]=max(lcma[fi[0]],fi[1])
        else:
          lcma[fi[0]]=fi[1]
    l=1
    for k,v in lcma.items():
      l*=pow(k,v,mod)
      l%=mod
    ans=0
    for ai in a:
      ans+=l*pow(ai,mod-2,mod)
      ans%=mod
    print(ans)

main()
### BUGGY CODE ###

x=int(input())
for i in range(-1000,1000):
  for j in range(-1000,1000):
    if i**5-j**5==x:
      print(i,j)
      break

### FIXED CODE ###

x=int(input())
a=0
b=0
for i in range(500):
  for j in range(-1000,1000):
    if i**5-j**5==x:
       a=i
       b=j
       break
print(a,b)
### BUGGY CODE ###

def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))
AF = [A[i]*F[i] for i in range(N)]

afmax = max(AF)

def can(max_af):
  k = K
  for i in range(N):
    af = AF[i]
    if af>max_af:
      max_ai = max_af // F[i]
      k -= A[i]-max_ai
      if k<0:
        return False
  return k>=0

l = -1
r = afmax
while r-l>1:
  m = (l+r)//2
  if can(m):
    r = m
  else:
    l = m
print(r)



### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))
AF = [A[i]*F[i] for i in range(N)]

afmax = max(AF)

def can(max_af):
  k = K
  for i in range(N):
    af = AF[i]
    if af>max_af:
      max_ai = max_af // F[i]
      k -= A[i]-max_ai
      if k<0:
        return False
  return k>=0

l = -1
r = afmax
while r-l>1:
  m = (l+r)//2
  if can(m):
    r = m
  else:
    l = m
print(r)
### BUGGY CODE ###

num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
trains_cumulative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        trains_cumulative_sum[start][arrive] = trains_cumulative_sum[start][arrive - 1] + trains[start][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = 0
    for j in range(start, arrive + 1):
        result += trains_cumulative_sum[j][arrive]
    print(result)


### FIXED CODE ###

num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
cumlative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] = cumlative_sum[start][arrive - 1] + trains[start][arrive]

for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] += cumlative_sum[start - 1][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = cumlative_sum[arrive][arrive] - cumlative_sum[start - 1][arrive] - cumlative_sum[arrive][start - 1] + cumlative_sum[start - 1][start - 1]
    print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                if dists[ny][nx] <= dists[y][x] + 4: break # gori~~
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()