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

S = input()

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
M = 10**9+7

for i in range(len(S)):
    if S[-i-1] == "?":
        for k in range(10):
            r = (k*10**i)%13
            for j in range(13):
                dp[i+1][(r+j)%13] += (dp[i][j]%M)
    else:
        r = (int(S[-i-1])*10**i)%13
        for j in range(13):
            dp[i+1][(r+j)%13] += (dp[i][j]%M)

ans = dp[-1][5] % M
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

import numpy as np

n = int(input())
a_array = np.array([int(elem) for elem in input().split(' ')])


def calculate_cumulative_sum(a_array, n):
    cumul_sum_array = np.zeros(n, dtype=np.int32)
    cumul_sum_array[0] = a_array[0]
    for i in range(1, n):
        cumul_sum_array[i] = cumul_sum_array[i - 1] + a_array[i]
    return cumul_sum_array


def check_1(cumul_sum_array):
    result = (cumul_sum_array != 0).all()
    return result


def check_2(cumul_sum_array):
    odd = np.sign(cumul_sum[::2])
    even = np.sign(cumul_sum[1::2])
    odd_sign = np.unique(odd)
    even_sign = np.unique(even)
    return (len(odd_sign) == 1) * (len(even_sign) == 1) * (odd_sign[0] != even_sign[0])


cumul_sum = calculate_cumulative_sum(a_array, n)
count = {'plus': 0, 'minus': 0}

def calc_num_manipulation(cumul_sum, start, n):
    cumul_sum = cumul_sum.copy()
    count = 0
    if check_1(cumul_sum) and check_2(cumul_sum):
        return count
    
    for i in range(n):
        if i == 0:
            diff = cumul_sum[i] - start
            count += abs(diff)
            cumul_sum[i:] -= diff
        else:
            if cumul_sum[i - 1] < 0 and cumul_sum[i] <= 0:
                diff = cumul_sum[i] - 1
                count += abs(diff)
                cumul_sum[i:] -= diff
            elif cumul_sum[i - 1] > 0 and cumul_sum[i] >= 0:
                diff = cumul_sum[i] - (-1)
                count += abs(diff)
                cumul_sum[i:] -= diff
            else:
                continue
    return count

count['plus'] = calc_num_manipulation(cumul_sum, 1, n)
count['minus'] = calc_num_manipulation(cumul_sum, -1, n)
print(min(count.values()))


### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split(' ')))

def count_manipulation(a_list, start):
    assert start in (0, 1)
    sum = 0
    count = 0
    for i, a in enumerate(a_list):
        sum += a
        if i % 2 == start:
            if sum > 0:
                continue
            else:
                diff = 1 - sum
                count += diff
                sum += diff
        else:
            if sum < 0:
                continue
            else:
                diff = sum - (-1)
                count += diff
                sum -= diff
    return count

count_plus = count_manipulation(a_list, 0)
count_minus = count_manipulation(a_list, 1)
print(min(count_plus, count_minus))
### BUGGY CODE ###

N = int(input())
s = list(map(int,input().split()))
count = 0
for i in range(N):
  for j in range(i + 1,N):
    if s[i] == s[j]:
      print("NO")
      count += 1
      break
if count == 0:
  print("YES")

### FIXED CODE ###

N = int(input())
s = list(map(int,input().split()))
count = 0
s.sort()

for i in range(N - 1):
  if s[i] == s[i + 1]:
    print("NO")
    count += 1
    break
    
if count == 0:
  print("YES")
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([[0,0,1]])
used={(0,0)}
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or (x,y) in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))
### BUGGY CODE ###

import numpy as np
n=int(input())
s=input()

r=[]
g=[]
b=[]

for i in range(0,n):
    if s[i]=='R':
        r.append(i)

    elif s[i]=='G':
        g.append(i)

    elif s[i]=='B':
        b.append(i)

s3=0
rl=len(r)
gl=len(g)
bl=len(b)

for i in range(0,n-2):
    for j in range(i,n-1):
        k=2*j-i
        if k<=n-1:
            
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                s3+=1
s2=rl*gl*bl-s3
print(s2)

### FIXED CODE ###

import numpy as np
n=int(input())
s=input()

r=[]
g=[]
b=[]

for i in range(0,n):
    if s[i]=='R':
        r.append(i)

    elif s[i]=='G':
        g.append(i)

    elif s[i]=='B':
        b.append(i)

s3=0
rl=len(r)
gl=len(g)
bl=len(b)

for i in range(0,n-2):
    n2=int((n+i)/2)+1
    for j in range(i,n2):
        k=2*j-i
        if k<=n-1:
            
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                s3+=1
s2=rl*gl*bl-s3
print(s2)
### BUGGY CODE ###

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

for i in range(Q):
  l, r = map(int, input().split())
  tmp = S[l-1:r]
  print((r - l + 1 - len(tmp.replace('AC', '')))//2)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
f = [0] * N
for i in range(N-1):
  add = 0
  if S[i:i+2] == 'AC':
    add = 1
  if i == 0:
    f[i+1] = add
  else:
    f[i+1] = f[i] + add

#print(f)
for i in range(Q):
  l, r = map(int, input().split())
  print(f[r-1]-f[l-1])
### BUGGY CODE ###

alp="abcdefghijklmnopqrstuvwxyz"

n=int(input())
s=list(input())
q=int(input())

for i in range(q):
    que=input().split()
    if que[0]=="1":
        s[int(que[1])-1]=que[2]
    else:
        print(len(set(s[int(que[1])-1:int(que[2])])))

### FIXED CODE ###

alp="abcdefghijklmnopqrstuvwxyz"

n=int(input())
s=list(input())
q=int(input())

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################



class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

app=[[0 for i in range(n)] for i in range(26)]
for i in range(n):
    app[alp.index(s[i])][i]=1

appapp=[None for i in range(26)]
for i in range(26):
    appapp[i]=SegTree(app[i], segfunc, ide_ele)

for i in range(q):
    que=input().split()
    if que[0]=="1":
        for tre in appapp:
            tre.update(int(que[1])-1,0)
        nex=alp.index(que[2])
        appapp[nex].update(int(que[1])-1,1)
    else:
        tab=0
        for tre in appapp:
            if tre.query(int(que[1])-1,int(que[2]))>0:
                tab+=1
        print(tab)
### BUGGY CODE ###

N = int( input() )
char_list = []
counter = 0 
for i in range(N):
    c = sorted( input() )
    char_list.append(c)
for i in range(N):
    for j in range(i+1, N):
        if char_list[i] == char_list[j]:
            counter += 1
print(counter)

### FIXED CODE ###

import collections
N = int( input() )
char_list = []
ans = 0 
for i in range(N):
    c = sorted( input() ) 
    c_new = "".join(c)
    char_list.append(c_new)
    
t = collections.Counter(char_list)

for i in t.values():
    if i != 1:
        ans += int( ( i * (i - 1) ) / 2 )
        
print(ans)
### BUGGY CODE ###

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

val = []
heavy = []

for x in A:
    if x in heavy:
        val[heavy.index(x)] += 1
    else:
        heavy.append(x)
        val.append(1)

for i in range(Q):
    B, C = input().split()
    B = int(B)
    C = int(C)
    if C not in heavy:
        heavy.append(C)
        val.append(0)
    if B in heavy:
        val[heavy.index(C)] += val[heavy.index(B)]
        val[heavy.index(B)] = 0
    sum = 0
    for x, y in zip(val, heavy):
        sum += x * y
    print(sum)


### FIXED CODE ###

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

heavy = [0] * (10 ** 5 + 1)
for x in A:
    heavy[x] += 1
suma = sum(A)

for i in range(Q):
    B, C = map(int, input().split())
    suma -= B * heavy[B]
    suma += C * heavy[B]
    heavy[C] += heavy[B]
    heavy[B] = 0
    print(suma)
### BUGGY CODE ###

N = int(input())  # Read N Number of integers
A = list(map(int, input().split(' ')))  # read the sequence of A
Q = int(input())   # read Q from user
def myindex(num1, num2, default=False):  # create the Function myindex 
    if num2 in num1:
        return num1.index(num2)
    else:
        return default
 
list1 = []  # create a list 
for a in range(0, Q): # for loop to get B and C
  c = list(map(int, input().split(' ')))
  t = myindex(A, c[0], -1)
  while t != -1:
    A[t] = c[1]
    t = myindex(A, c[0], -1)
  F = sum(A)
  list1.append(F) # add to the list1 
for s in list1:
  print(s) 

### FIXED CODE ###

N = raw_input()
ns = raw_input()
ns = ns.split(' ')

data = {}
for i in ns:
    i = int(i)
    if i in data:
        data[i] += 1
    else:
        data[i] = 1

Q = raw_input()
opr = []
for _ in range(int(Q)):
    tmp = raw_input()
    tmp = tmp.split(' ')
    opr.append([int(tmp[0]), int(tmp[1])])

ans = 0
for k, v in data.iteritems():
    ans += k * v
for op in opr:
    if op[0] not in data:
        print ans
        continue

    old1 = data[op[0]]
    del data[op[0]]

    old2 = 0
    if op[1] in data:
        old2 = data[op[1]]
    ans -= old1 * op[0] + old2 * op[1]

    data[op[1]] = old1 + old2
    ans += data[op[1]] * op[1]

    print ans
### BUGGY CODE ###

S = input()[::-1]

counts = [0] * 2019
counts[0] = 1

a = 1
d = 0

for s in S:
    d = d + int(s)*a
    num = d%2019
    counts[num] += 1
    a *= 10

ans = 0

for i in counts:
    if i >=2:
        x = (i*(i-1))//2
        ans += x

print(ans)

### FIXED CODE ###

#ACの人のやつ丸パクリです。自分のソースコードがTLEになるので試しに使わせてもらいます。

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

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

### FIXED CODE ###

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

import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(a[c],i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":q=int(q);b=s[q-1];a[b].pop(bisect.bisect_left(a[b],q));bisect.insort(a[r],q);s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):
                d+=1
        print(d)

### FIXED CODE ###

import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(a[c],i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":
        q=int(q)
        b=s[q-1]
        if b!=r:
            a[b].pop(bisect.bisect_left(a[b],q))
            bisect.insort(a[r],q)
            s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):
                d+=1
        print(d)
### BUGGY CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1 and cord[y][x+i] != '@':
                l.append((x+i,y))
            else:
                f1 = False
            if f2 and cord[y][x-i] != '@':
                l.append((x-i,y))
            else:
                f2 = False
            if f3 and cord[y+i][x] != '@':
                l.append((x,y+i))
            else:
                f3 = False
            if f4 and cord[y-i][x] != '@':
                l.append((x,y-i))
            else:
                f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = '#'
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
print(bfs(xg,yg))

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1:
                if cord[y][x+i] == '.':
                    l.append((x+i,y))
                elif cord[y][x+i] == '@' or cord[y][x+i] != dep+1:
                    f1 = False
            if f2:
                if cord[y][x-i] == '.':
                    l.append((x-i,y))
                elif cord[y][x-i] == '@' or cord[y][x-i] != dep+1:
                    f2 = False
            if f3:
                if cord[y+i][x] == '.':
                    l.append((x,y+i))
                elif cord[y+i][x] == '@' or cord[y+i][x] != dep+1:
                    f3 = False
            if f4:
                if cord[y-i][x] == '.':
                    l.append((x,y-i))
                elif cord[y-i][x] == '@' or cord[y-i][x] != dep+1:
                    f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
#print(len(cord),len(cord[0]))

print(bfs(xg,yg))
### BUGGY CODE ###

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

ans = []
for i in range(0, N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            ans.append((S[i] != S[j] and S[i] != S[k] and S[j] != S[k]) and j - i != k - j)

print(sum(ans))

### FIXED CODE ###

# D - RGB Triplets

N = int(input())
S = input()
cnt_R = S.count('R')
cnt_G = S.count('G')
cnt_B = S.count('B')
total = cnt_R * cnt_G * cnt_B

expt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if k < N and (S[i] != S[j] and S[j] != S[k] and S[i] != S[k]):
            expt += 1

print(total - expt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

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

p1 = 0
p2 = 0
P1 = np.zeros(N+1)
P2 = np.zeros(N+1)
for i, a in enumerate(A):
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1[N-1-i] = p1
    P2[N-1-i] = p2

S = sum(A)
"""
dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N] = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[i][0] = max(dp[i+1][0], P1[i])
    dp[i][1] = max(dp[i+1][1], P2[i]+dp[i][0])
    dp[i][2] = min(dp[i+1][2], P2[i]-dp[i][1])
    dp[i][3] = min(dp[i+1][3], P1[i]+dp[i][2])
"""

dp = np.zeros((N+1, 4), dtype=int)
dp[0, :] = np.array([P1[0], P1[0]+P2[0], -P1[0], 0])
for i, (p1, p2) in enumerate(zip(P1, P2)):
    if i == 0: continue
    dp[i, 0] = np.maximum(dp[i-1, 0], p1)
    dp[i, 1] = np.maximum(dp[i-1, 1], p2+dp[i, 0])
    dp[i, 2] = np.minimum(dp[i-1, 2], p2-dp[i, 1])
    dp[i, 3] = np.minimum(dp[i-1, 3], p1+dp[i, 2])

print(dp[N, 3]+S)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

p1 = 0
p2 = 0
P1 = [0]
P2 = [0]
for a in A:
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1.append(p1)
    P2.append(p2)

S = sum(A)
dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N] = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[i][0] = max(dp[i+1][0], P1[i])
    dp[i][1] = max(dp[i+1][1], P2[i]+dp[i][0])
    dp[i][2] = min(dp[i+1][2], P2[i]-dp[i][1])
    dp[i][3] = min(dp[i+1][3], P1[i]+dp[i][2])

print(dp[0][3]+S)
### BUGGY CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=sorted(l)

while m>0:
    a=l[len(l)-1]
    l.pop()
    l.append(a//2)
    l=sorted(l)
    m=m-1

print(sum(l))


### FIXED CODE ###

import heapq

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=list(map(lambda x: -x,l))

heapq.heapify(l)

while m>0:
    a=heapq.heappop(l)
    if a//2==a/2:
        heapq.heappush(l,a//2)

    else:
        heapq.heappush(l,a//2+1)
    m=m-1

print(-sum(l))
### BUGGY CODE ###

import sys, itertools
input = sys.stdin.readline

def main():
    N = int(input())
    memo = []
    count = 0
    for s in sys.stdin.readlines():
        if s.rstrip() in memo:
            count += 1
        else:
            memo.append(s.rstrip())
        
    print(N - count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys, itertools
input = sys.stdin.readline

def main():
    N = int(input())
    S = [s.rstrip() for s in sys.stdin.readlines()]
    count = 0

    memo = sorted(S)

    for i in range(N - 1):
        if memo[i] == memo[i + 1]:
            count += 1
        
    print(N - count)

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

def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	while Q:
		f = Q.popleft()
		inQ[f] = False
		for t, c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					Q.append(t)
					inQ[t] = True
					cnt[t] += 1
					front = Q.popleft()
					if d[front] > dist:
						Q.append(front)
					else:
						Q.appendleft(front)
				if cnt[t] > V:
					# negative cycle
					return None
	return d


def main():
	n, m, *L = map(int, open(0).read().split())
	con = [[] for _ in range(n)]
	g = []
	c = [True] * n
	for s, t in zip(*[iter(L)] * 2):
		con[s - 1] += [(t - 1, - 1)]
		c[t - 1] = False
	for i in range(n):
		if c[i]:
			root = i
			break
	dist = SPFA(con, root)
	ans = [0] * n
	for s, t in zip(*[iter(L)] * 2):
		if dist[t - 1] == dist[s - 1] - 1:
			ans[t - 1] = s
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()

### FIXED CODE ###

def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	rev = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		rev[t - 1].append(s - 1)
		deg[t - 1] += 1
	order = topologicalSort(g, deg)
	idx = [None] * v
	for i, o in enumerate(order):
		idx[o] = i
	ans = [0] * v
	for i in range(v):
		if rev[i]:
			ans[i] = max(rev[i], key=lambda x: idx[x]) + 1
	print("\n".join(map(str, ans)))

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

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy,"n"))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
while len(q)!=0:
  x,y,d=q.popleft()
  c=cost[y][x]
  for i in range(1,k+1):
    if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
      cost[y][x+i]=c+1
      if d=="r":
        q.appendleft((x+i,y,"r"))
      else:
        q.append((x+i,y,"r"))
    else:
      break
  for i in range(1,k+1):
    if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
      cost[y][x-i]=c+1
      if d=="l":
        q.appendleft((x-i,y,"l"))
      else:
        q.append((x-i,y,"l"))
    else:
      break
  for i in range(1,k+1):
    if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
      cost[y+i][x]=c+1
      if d=="d":
        q.appendleft((x,y+i,"d"))
      else:
        q.append((x,y+i,"d"))
    else:
      break
  for i in range(1,k+1):
    if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
      cost[y-i][x]=c+1
      if d=="u":
        q.appendleft((x,y-i,"u"))
      else:
        q.append((x,y-i,"u"))
    else:
      break
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

### FIXED CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])