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

q = int(input())

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5) + 1):
        # 既にfalseになってたらスキップ
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
prime_ls = primes(10**5)

def isOK(index, key, l):
    if l[index] >= key:
        return True
    else:
        return False

def meguru_search(l, key):
    left = -1
    right = len(l)

    while (right - left) > 1:
        mid = left + (right - left) // 2
        # 直感的に記憶　
            # 「含まれている」んだったら「含むを許容（等号付き）する右側」はmidまで動かして問題ない
                # 新しいrightの位置がkeyの位置だとしても、「含む」は許容されてる
            # 「含まれていない」んだったら「含まない(<)左の壁」をそこまで動かしてもkeyを通り過ぎることはない
        if isOK(mid, key, l):
            right = mid
        else:
            left = mid
    
    # whileを抜ける時、rightとleftは一個差で、かつkeyがrightの位置にある
    return right

def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return True
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return False

ans_ls = [0] * q
for i in range(q):
    l,r = map(int,input().split())
    start = meguru_search(prime_ls, l)
    end = meguru_search(prime_ls, r)
    target = prime_ls[start:end+1]
    ans = 0
    # ↓ここで枝切りしてから、「+1」の条件をチェックしたい
    for prime in target:
        if binary_search(prime_ls, (prime + 1)// 2):
                ans += 1
    ans_ls[i] = ans
for ans in ans_ls:
    print(ans)


### FIXED CODE ###

q = int(input())

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5) + 1):
        # 既にfalseになってたらスキップ
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return is_prime
prime_ls = primes(10**5)

csum = [0] * (10**5)
for i in range(1,10**5):
    if prime_ls[i]:
        if prime_ls[(i+1) // 2]:
            csum[i] = csum[i-1] + 1
        else:
            csum[i] = csum[i-1]
    else:
        csum[i] = csum[i-1]

ans_ls = [0] * q
for i in range(q):
    l,r = map(int,input().split())
    ans_ls[i] = csum[r] - csum[l-1]
for ans in ans_ls:
    print(ans)
### BUGGY CODE ###

from math import factorial

N = int(input())
S = list(''.join(sorted(str(input()))) for _ in range(N))
unique_S = list(set(S))

ans = 0
for s in unique_S:
    n = S.count(s)
    if n > 1:
        ans += factorial(n) // (factorial(n - 2) * factorial(2))
print(ans)


### FIXED CODE ###

N = int(input())
S = list(''.join(sorted(str(input()))) for _ in range(N))

dic = {}
ans = 0

for s in S:
    if not s in dic:
        dic[s] = 1
    else:
        ans += dic[s]
        dic[s] += 1
print(ans)
### BUGGY CODE ###

## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*INF+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, INF)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt, hn*INF+wn))
    # 魔法
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt+1, hn*INF+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)
### BUGGY CODE ###

from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
for i in range(1, len(S) + 1):
    s += (int(S[-i]) * ((10 ** (i - 1)) % 2019))
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)


### FIXED CODE ###

from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    # s += int(S[i]) * ((10 ** (len(S) - 1 - i)) % 2019)
    # s %= 2019
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    kurai %= 2019
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)
### BUGGY CODE ###

n = int(raw_input())
A = map(int,raw_input().split())

import numpy

mat = []
for q in range(n-1):
  mat.append( [0]*q + [0.5,0.5] + [0]*(n-q-2) )
mat.append([0.5] + [0]*(n-2) + [0.5])

X = numpy.matrix(mat)

mat2 = []
for q in A:
  mat2.append([q])
Y = numpy.matrix(mat2)
ans = numpy.linalg.solve(X,Y)
ans = map(int,ans)
print ' '.join(map(str, ans))  

### FIXED CODE ###

n = int(raw_input())
A = map(int,raw_input().split())
S = 0
inv = [1,-1]*(n//2) + [1]
for q in range(n):
  S += A[q]*inv[q]
ans = [0]*n
for q in range(n):
  ans[q] = S
  S = 2*A[q]-S
print ' '.join(map(str, ans))
### BUGGY CODE ###

s = input()
t = input()

dp = [0] * (len(s)+1)
dps = [[] for _ in range(len(s)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    for j in range(1, len(s)+1):
        sj = s[j-1]
        if ti == sj:
            dp[j] = dp[j-1] + 1
            temp = dps[j-1][:]
            temp.append(ti)
            dps[j] = temp
        else:
            if dp[j-1] >= dp[j]:
                dp[j] = dp[j-1]
                dps[j] = dps[j-1][:]
print(''.join(dps[-1]))


### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1][:]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)
### BUGGY CODE ###

from collections import deque

N = int(input())
C = deque(list(input()))

cnt = 0

while len(set(C)) > 1:
    if C[0] == 'W' and C[-1] == 'R':
        cnt += 1
        C.popleft()
        C.pop()
    else:
        if C[0] == 'R':
            C.popleft()
        if C[-1] == 'W':
            C.pop()

print(cnt)

### FIXED CODE ###

from collections import deque

N = int(input())
C = deque(list(input()))

cnt = 0

while len(C) > 1:
    if C[0] == 'W' and C[-1] == 'R':
        cnt += 1
        C.popleft()
        C.pop()
    else:
        if C[0] == 'R':
            C.popleft()
        if C[-1] == 'W':
            C.pop()

print(cnt)
### BUGGY CODE ###

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

all_data = list(set(A))

num = 0

for i in all_data:
  tmp = A.count(i) + A.count(i+1) + A.count(i-1)
  num = max(num, tmp)
  
print(num)



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0]*(100000+2)

for i in A:
  ans[i-1] += 1
  ans[i] += 1
  ans[i+1] += 1

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

n = int(input())
a = list(map(int, input().split()))
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()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

if x>200:
  a.sort()
  a.reverse()
  a=a[0:200]

if y>200:
  b.sort()
  b.reverse()
  b=b[0:200]

if z>200:
  c.sort()
  c.reverse()
  c=c[0:200]

ansList=[]
for m in range(len(a)):
  for n in range(len(b)):
    for o in range(len(c)):
      ansList.append(a[m]+b[n]+c[o])

ansList.sort()
ansList.reverse()

for i in range(k):
  print(ansList[i])


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])
### 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):
        if a[j] % g == 0:
            pass
        else:
            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 ###

n, k = map(int,input().split())
arr = []
for i in range(n):
    a,b = map(int,input().split())
    arr += [a] * b

arr.sort()
print(arr[k - 1])

### FIXED CODE ###

n, k = map(int,input().split())
arr = []
for _ in range(n):
    a,b = map(int,input().split())
    arr.append([a,b])
arr.sort()
for i in arr:
    k -= i[1]
    if k <= 0:
        print(i[0])
        break
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans *= a[i]
if ans > 10**18:
    print('-1')
else:
    print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
    exit()
a.sort(reverse = True)
ans = 1
for i in range(N):
    ans *= a[i]
    if ans > 10**18:
        print('-1')
        break
else:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def input():
    return sys.stdin.readline()[:-1]


def main():
    N = int(input())
    a = [-1]+list(map(int, input().split()))
    b = [0] * (N+1)
    for i in reversed(range(1,N+1)):
        total = 0
        for j in range(i,N+1):
            if i%j==0:
                total += b[j]
        if a[i] != (total%2):
            b[i] = 1
    ans = []
    cnt = 0
    for i, n in enumerate(b):
        if n!=0:
            ans.append(i)
            cnt += 1
    print(cnt)
    print(*ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def input():
    return sys.stdin.readline()[:-1]


def main():
    N = int(input())
    a = [-1]+list(map(int, input().split()))
    b = [0] * (N+1)
    for i in reversed(range(1,N+1)):
        total = 0
        for j in range(i,N+1,i):
            total += b[j]
        if a[i] != (total%2):
            b[i] = 1
    ans = []
    cnt = 0
    for i, n in enumerate(b):
        if n!=0:
            ans.append(i)
            cnt += 1
    print(cnt)
    print(*ans)

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

# 所持している鍵の集合をbitで表現する
#　鍵の集合を表す2進数が少なくなる方向に遷移することはないから，for文for文でかける

N, M = map(int, input().split())
status_money = [float('inf')] * (1 << N)

# 初期状態からの遷移を記録
for _ in range(M) :
    a, b = map(int, input().split())
    C = 0
    for c in input().split() :
        C |= (1 << int(c) - 1)
    status_money[C] = min(status_money[C], a)
    
# ある状態とある状態の組合せを全部取る
for c in range(1 << N):
    # どんな鍵の組合せでも到達できない宝箱の組合せがあるかもしれない
    if status_money[c] == float('inf'):
        continue
    for d in range(1 << N):
        # c と d の論理和をとって新しく生成される状態 e を考える
        e = c | d
        # eにあらかじめ格納されている最小コストと，今生成したコストとのminをとる
        status_money[e] = min(status_money[c] + status_money[d], status_money[e])

# そもそも到達できない場合の処理を記述       
if status_money[-1] == float('inf'):
    print(-1)
else:
    print(status_money[-1])

### FIXED CODE ###

# 所持している鍵の集合をbitで表現する
#　鍵の集合を表す2進数が少なくなる方向に遷移することはないから，for文for文でかける

N, M = map(int, input().split())
status_money = [float('inf')] * (1 << N)

# 初期状態からの遷移を記録
for _ in range(M) :
    a, b = map(int, input().split())
    C = 0
    for c in input().split() :
        C |= (1 << (int(c) - 1))
    status_money[C] = min(status_money[C], a)
    
# ある状態とある状態の組合せを全部取る
for c in range(1 << N):
    # どんな鍵の組合せでも到達できない宝箱の組合せがあるかもしれない
    if status_money[c] == float('inf'):
        continue
    for d in range(1 << N):
        # c と d の論理和をとって新しく生成される状態 e を考える
        e = c | d
        # eにあらかじめ格納されている最小コストと，今生成したコストとのminをとる
        status_money[e] = min(status_money[c] + status_money[d], status_money[e])

# そもそも到達できない場合の処理を記述       
if status_money[-1] == float('inf'):
    print(-1)
else:
    print(status_money[-1])
### BUGGY CODE ###

from operator import mul
from functools import reduce
n = input()
l = [int(e) for e in input().split(" ")]
res = 1
res = reduce(mul,l)
if res > 1e+18:
    print("-1")
else:
    print(res)

### FIXED CODE ###

from operator import mul
from functools import reduce
n = input()
tmp = input().split(" ")
l = sorted([int(e) for e in tmp])
def solve():
    res = 1
    for e in l:
        res = e*res
        if res > 1e+18:
            print("-1")
            return
    print(res)
solve()
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]
    
    

    

    bh_destroy = bomb_most_h[1]
    

    bw_destroy = bomb_most_w[1]
    

    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    
    ans = 0
    
    for bh in candidate_h:
        for bw in candidate_w:   
            if [bh,bw] in BOMB_HW:
                ans = max(bh_destroy+bw_destroy-1,ans)
            else:
                ans = max(bh_destroy+bw_destroy,ans)
    print(ans)
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    dd = defaultdict(bool)
    for m in range(M):
        dd[str(bomb_h[m]) + "-" + str(bomb_w[m])] = True
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]

    bh_destroy = bomb_most_h[1]
    bw_destroy = bomb_most_w[1]
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    ans = bh_destroy+bw_destroy
    

    for bh in candidate_h:
        for bw in candidate_w:   
            if not(dd[str(bh) + "-" + str(bw)]):
                print(ans)
                sys.exit()
    print(ans-1)
    


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

import sys
import heapq
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
ans = [[-1,-1] for i in range(n)]
ans[ne] = [0,0]
def dfs(x,y,z):
        for i in g[x]:
                if i == y:
                        continue
                if ans[i][1] < z+1:
                        ans[i] = [x+1,z+1]
                        heapq.heappush(que,[z+1,i,x])
que = [[0,ne,-1]]
heapq.heapify(que)
while que:
        c,a,b = heapq.heappop(que)
        dfs(a,b,c)
for i,j in ans:
        print(i)

### FIXED CODE ###

import sys
import heapq
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
kazu = [0]*n
for i in range(n):
        kazu[i] = len(g2[i])
ans = [0] * n
def dfs(x):
        z = []
        for i in g[x]:
                kazu[i]-=1
                if kazu[i] == 0:
                        z.append(i)
                        ans[i] = x+1
        for i in z:
                dfs(i)
dfs(ne)
for i in ans:
        print(i)
### BUGGY CODE ###

N = int(input())
inputs = [int(i) for i in input().split()]

ans = 0

for i in range(N):
    total = 0
    for item in inputs[i:]:
        total += item
        if total == 0:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())
inputs = [int(i) for i in input().split()]

ans = 0
ruisekiwa = [0] * (N+1)

for i in range(N):
    ruisekiwa[i+1] = ruisekiwa[i] + inputs[i]

ruisekiwa = ruisekiwa[1:]
ruisekiwa.sort()
counter_ruiseki = Counter(ruisekiwa)

for key, value in counter_ruiseki.items():
    if key == 0 and value == 1:
        ans += value
        continue
    elif key == 0 and value > 1:
        ans += value
    if value > 1:
        ans += sum(list(range(value)))

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

n, k = map(int,input().split())
p = list(input())
a = []
ape = 1
for i in range(1,n):
     if p[i-1] != p[i]:
          a.append(ape)
          ape = 1
     else:
          ape += 1
a.append(ape)

def count(a,k,i,start):#start = p[0],a[i]からスタート
     ans = 0
     if start == '1':
          if i%2 == 0:
               for j in range(2*k+1):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
          else:
               for j in range(2*k):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
     else:
          if i%2 == 1:
               for j in range(2*k+1):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
          else:
               for j in range(2*k):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
     return ans

ans = count(a,k,0,p[0])
if (p[0] == '1') or (len(a) == 1):
     kaisi = 0
else:
     kaisi = 1
for i in range(kaisi,len(a),2):
     ans = max(count(a,k,i,p[0]), ans)
print(ans)

### FIXED CODE ###

#参考　https://atcoder.jp/contests/abc124/submissions/4948803
from itertools import accumulate

n, k = map(int,input().split())
p = list(input())
a = []
pre = '1'
cnt = 0
for i in range(n):
     if pre != p[i]:
          a.append(cnt)
          cnt = 1
          pre = p[i]
     else:
          cnt += 1
a.append(cnt)
if pre == '0':
     a.append(0)

w = 2*k+1

if w >= len(a):
     print(n)
else:
     acc = list(accumulate(a))
     ans = 0
     acc = [0] + acc
     for i in range(0,len(a)-w+1,2):
          ans = max(ans,acc[i+w]-acc[i])
     print(ans)
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[-1] * W for _ in range(H)]
    q = [(0, x1, y1)]
    while q:
        d, i, j = heappop(q)
        if dist[i][j] >= 0: continue
        dist[i][j] = d
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] >= 0: continue
                heappush(q, (d + 1, ni, nj))
    print(dist[x2][y2])

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)