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

#A問題
import sys
sys.setrecursionlimit(500000)
N=int(input())
S=str(input())
Slist=list(S)
count=-1
kari=[]
def ans(n):
    global count
    global Slist
    if n == N-1:
        if Slist[n] in kari:
            count+=1
            return
        else:
            count+=2
            return
    else:
        if Slist[n] in kari:
            ans(n+1)
        else:
            kari.append(Slist[n])
            ans(n+1)
            kari.remove(Slist[n])
            ans(n+1)
ans(0)
count%=1000000007
print(count)

### FIXED CODE ###

#A問題
import collections
N=int(input())
S=str(input())
Slist=list(S)
c = collections.Counter(Slist)
d = c.most_common()
dlen=len(d)
count=1
for i in range(dlen):
    count*=(d[i][1]+1)
count-=1
count%=1000000007
print(count)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    k = a[i]
    a[i] = 0
    print(max(a))
    a[i] = k
    

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
for i in range(n):
    if a[i] == b[-1]:
        print(b[-2])
    else:
        print(b[-1])
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(k):
        imos = [0 for _ in range(n)]

        for i, ai in enumerate(a):
            imos[max(0, i - ai)] += 1
            if i + ai + 1 < n:
                imos[i + ai + 1] -= 1

        val = 0
        for i, im in enumerate(imos):
            val += im
            # tmp = 1 if a[i] == 0 else 0
            a[i] = val

        if min(a) == n:
            break

    print(*a, sep=" ")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(min(k,42)):
        imos = [0 for _ in range(n)]

        for i, ai in enumerate(a):
            imos[max(0, i - ai)] += 1
            if i + ai + 1 < n:
                imos[i + ai + 1] -= 1

        val = 0
        for i, im in enumerate(imos):
            val += im
            a[i] = min(val, n)

        # if min(a) == n:
        #     break

    print(*a, sep=" ")


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

import numpy as np

n = int(input())
l = np.array(list(map(int, input().split())))

l = np.sort(l)[::-1]

cnt = 0
for a in range(n):
    for b in range(a + 1, n):
        for c in range(b + 1, n):
            if l[a] < (l[b] + l[c]) and l[b] < (l[a] + l[c]) and l[c] < (l[a] + l[b]):
                cnt += 1
            else:
                break

print(cnt)


### FIXED CODE ###

import numpy as np
import bisect

n = int(input())
l = np.array(list(map(int, input().split())))

# l.sort()

# ans = 0
# for a in range(n - 2):
#     for b in range(a + 1, n - 1):
#         ans += bisect.bisect_left(l, l[a] + l[b]) - (a + 1)
# print(ans)

res = 0
l = sorted(l)
for i in range(1, n - 1):
    b = l[i]
    for j in range(0, i):
        a = l[j]
        res += bisect.bisect_left(l, a + b) - (i + 1)
print(res)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for i in range(N):
    mi = min(P[:i+1])
    if P[i] <= mi:
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
mi = P[0]
for i in range(N):
    if mi > P[i]:
        mi = P[i]
    if P[i] <= mi:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = np.array(list(map(int, input().strip().split()))) - 1
    mask = 0b0
    for i in c:
        mask |= 0b1 << i

    for j in range(1 << n):
        if dp[j] < float('inf'):
            dp[j | mask] = min(dp[j] + a, dp[j | mask])

print(dp[(1 << n) - 1] if dp[(1 << n) - 1] < float('inf') else -1)

### FIXED CODE ###

n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
U = [0]*n

for i in range(n):
    U[i] = (P[i]+1)/2

ans = sum(U[:k])

for j in range(1, n-k+1):
    t = 0
    for i in range(j, j+k):
        t += U[i]
    if ans < t:
        ans = t
print(ans)


### FIXED CODE ###

import copy
n, k = map(int, input().split())
P = list(map(int, input().split()))
U = [0]*n

for i in range(n):
    U[i] = (P[i]+1)/2

ans = sum(U[:k])
t = copy.copy(ans)

for i in range(n-k):
    t =  t+U[k+i]-U[i]
    ans = max(ans, t)
    
print(ans)
### BUGGY CODE ###

def num_divisors_table(n):
    table=[0]*(n+1)

    for i in range(1,n+1):
        for j in range(i,n+1,i):
            table[j]+=1
    
    return table

N=int(input())
table=num_divisors_table(N)
ans=0
for K in range(1,N+1):
    ans+=K*table[K]
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
    m=N//i
    ans+=m*i*(m+1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
import math
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def yakusu(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num


ans = 0
for i in range(1, N+1):
    ans = yakusu(i)*i+ans

print(ans)


### FIXED CODE ###

N = int(input())
ans=0

#初項a、公差d=a、n項までの和
for a in range(1,N+1):
    n=N//a
    ans=(n*(2*a+(n-1)*a))//2+ans
print(ans)
### BUGGY CODE ###

import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

N, M = map(int, input().split())
G = nx.Graph()

for i in range(N):
    G.add_node(i+1)

for i in range(M):
    a,b = map(int, input().split())
    G.add_edge(a,b)
    
pred, dist = nx.dijkstra_predecessor_and_distance(G, 1)

pred = sorted(pred.items())

print("Yes")
for i in range(1,N):
    print(pred[i][1][0])

### FIXED CODE ###

import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

import heapq
import sys

input = sys.stdin.readline


N, M = map(int, input().split())

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    path = [-1] * N
    for a,b in edge[s]:
        path[b] = s
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:                
            if used[e[1]]:
                if path[e[1]] == -1:
                    path[e[1]] = v
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d, path

edge = [[] for i in range(N)]

for i in range(M):
    x,y = map(int,input().split())
    edge[x-1].append([1,y-1])
    edge[y-1].append([1,x-1]) 
    

d, path = dijkstra_heap(0, edge)

print("Yes")
for i in range(1,N):
    print(path[i]+1)
### BUGGY CODE ###

import bisect as bi

I=lambda : list(map(int,input().split()))
"""
n,m = I();md=10**9+7;p=0;a=1
dp=[0,1];l=[0]*(10**5+2)
for _ in range(m):
    x=int(input())
    l[x]=1
for i in range(1,n+1):
    if l[i]:
        dp.append(0)
    else:
        dp.append((dp[-1]+dp[-2])%md)
print(dp[-1])
"""
n,m = I()
l=I();s=sum(l);l.sort();d=[]
for _ in range(m):
    b,c=I()
    d.append([c,b])
p=s=0    
for i in sorted(d,reverse=True):
    if l[p]>=i[0]:
        break
    k = bi.bisect(l[p:],i[0])
    p+=min(k,i[1]);s+=i[0]*min(k,i[1])
    if p>=n:
        break
s+=sum(l[p:])
print(s)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, m = I()
a = sorted(I())
q = []
for i in range(m):
    q.append(I())
q.sort(key = lambda x: (x[1], x[0]), reverse = True)
cur = 0
for b, c in q:
    while cur < n and a[cur] >= c:
        cur += 1
    while cur < n and b and a[cur] < c:
        b -= 1
        a[cur] = c
        cur += 1
print(sum(a))
### BUGGY CODE ###

A, B, K = map(int, input().split())
P = [i for i in range(A, B+1)]
if (B - A + 1) > K * 2:
    del P[K:-K]
for i in P:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
if (B - A + 1) > K * 2:
    for i in range(A, A+K):
        print(i)
    for i in range(B - K+1, B+1):
        print(i)
else:
    for i in range(A, B+1):
        print(i)
### BUGGY CODE ###

def dfs(n,e,fordfs):
    P = [-1]*n
    L = [0]*n
    que = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.pop()
        for ne in fordfs[now]:
            if P[ne] == -1:
                L[ne] = L[now]+1
                P[ne] = now + 1
                que.append(ne)
            elif L[ne]<L[now]+1:
                L[ne] = L[now]+1
                P[ne] = now + 1
                que.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = dfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()


### FIXED CODE ###

def examD():
    N, M = LI()
    V = [[] for _ in range(N)]
    ans = [0]*N
    Cnt=[0]*(N+1); Cnt[N]=1
    for i in range(N+M-1):
        a, b = LI()
        V[a-1].append(b-1)
        Cnt[b-1] += 1
    root = Cnt.index(min(Cnt))
    que = [root]
#    print(Cnt)
#    print(root)
    while que:
        v = que.pop()
        for u in V[v]:
            if Cnt[u] == 1:
                ans[u] = v+1
                que.append(u)
            else:
                Cnt[u] -= 1
    print(*ans, sep='\n')
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

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

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(N+1):
            if j-1 < s or j-1 >= t:
                dp[i+1][j-1] = dp[i][j-1]
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

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

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        for k in range(j+1, n):
            c = l[k]
            if a + b > c:
                cnt += 1

print(cnt)

### FIXED CODE ###

from bisect import *

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

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        lower = max(j+1, bisect_right(l, b-a))
        upper = bisect_left(l, a+b)
        cnt += max(0, upper-lower)

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

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

ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        if (abs(j - i) == A[i] + A[j]):
            ans += 1

print(ans)


### FIXED CODE ###

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

L = []
R = []

ans = 0

for i in range(N):
    L.append(i + A[i])
    R.append(i - A[i])

r = collections.Counter(R)

for l in L:
    ans += r[l]

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

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys
from collections import deque


def _s(): return sys.stdin.readline().strip()


def _sa(): return sys.stdin.readline().strip().split()


def _i(): return int(sys.stdin.readline().strip())


def main():
    s = deque([c for c in _s()])
    q = _i()
    flip = 0
    for _ in range(q):
        tmp = _sa()
        op = int(tmp[0])
        if op == 1:
            flip ^= 1
        else:
            loc = int(tmp[1]) - 1
            c = tmp[2]
            if flip ^ loc:
                s.append(c)
            else:
                s.appendleft(c)

    ans = ""
    n = len(s)
    for _ in range(n):
        if flip == 0:
            ans += s.popleft()
        else:
            ans += s.pop()
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys
from collections import deque


def _s(): return sys.stdin.readline().strip()


def _sa(): return sys.stdin.readline().strip().split()


def _i(): return int(sys.stdin.readline().strip())


def main():
    s = deque([c for c in _s()])
    q = _i()
    flip = 0
    for _ in range(q):
        tmp = _sa()
        op = int(tmp[0])
        if op == 1:
            flip ^= 1
        else:
            loc = int(tmp[1]) - 1
            c = tmp[2]
            if flip ^ loc:
                s.append(c)
            else:
                s.appendleft(c)

    n = len(s)
    for _ in range(n):
        if flip == 0:
            print(s.popleft(), end="")
        else:
            print(s.pop(), end="")


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

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)


N, Q = map(int, input().split())
G = defaultdict(set)
X = [0 for _ in range(N)]
P = [0 for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x


def dfs(p, x, parent):

    P[p] += x + X[p]
    for node in G[p]:
        if node == parent:
            continue
        dfs(node, x + X[p], p)


dfs(0, 0, -1)

print(' '.join([str(p) for p in P]))


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

for j in range(Q):
  p, x = map(int, input().split())
  score[p-1] += x

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)
### BUGGY CODE ###

from math import ceil, sqrt

Q = int(input())
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(map(max, querys))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print(nums[ri] - nums[max(0, li - 2)])


### FIXED CODE ###

from math import ceil, sqrt

Q = int(input())
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(map(max, querys))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False
            break

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print(nums[ri] - nums[max(0, li - 2)])
### BUGGY CODE ###

N = int(input())
S = list(map(int,input().split()))
counter = 0
for i in range(N):
  for j in range(N-1-i):
    for k in range(N -2 -i -j):
      a = S[i]
      b = S[i+j+1]
      c = S[i+j+k+2]
      if (a + b > c) and (c > abs(a - b)) and (a + b > c):
        counter += 1
    
print(counter)

### FIXED CODE ###

import bisect
N = int(input())
List = list(map(int,input().split()))
List.sort()
ans = 0
for i in range(N-1):
  for j in range(i+1, N):
    ans += bisect.bisect_left(List,List[i]+List[j])-(j+1)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y)
    que = [(0, xs, ys)]
    inf = 10 ** 6 * k
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        # 現在のコストより高いなら無視する
        if cost > dp[x][y]:
            continue
        if x == xg and y == yg:
            return cost
        for i in range(4):
            for j in range(1, k+1):
                x_, y_ = x+j*dx[i], y+j*dy[i]
                if not field[x_][y_]:
                    break
                if dp[x_][y_] > dp[x][y] + 1:
                    dp[x_][y_] = dp[x][y] + 1
                    heappush(que, (dp[x_][y_], x_, y_))
    return dp[xg][yg]
        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    inf = 10 ** 6 * k
    for i in range(h):
        #False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    ans = dijkstra(xs,ys,xg,yg,h,w,k,field)
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()