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

#!/usr/bin/env python3
n = int(input()) 
A = list(map(int, input().split()))
q = int(input()) 
for i in range(q):
    b, c = map(str, input().split())
    if int(b) in A:
        A = [int(str(a).replace(b, c)) for a in A]
    print(sum(A))

### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
d = Counter(A)
Q = int(input())
ans = sum(A)
for i in range(Q):
    b, c = map(int, input().split())
    ans += (c-b) * d[b]
    d[c] += d[b]
    d[b] = 0
    print(ans)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
ID = [i for i in range(1, N+1)]
for i in range(M):
    L, R = list(map(int, input().split()))
    r = [i for i in range(L, R+1)]
    ID = set(ID) & set(r)
    if len(ID) == 0:
        print(0)
        exit()
if len(ID) > N:
    print(N)
else:
    print(len(ID))

### FIXED CODE ###

N, M = list(map(int, input().split()))
LR = [list(map(int,input().split())) for i in range(M)]
max = 1
min = 100000
for i in range(M):
    if max < LR[i][0]:
        max = LR[i][0]
    if min > LR[i][1]:
        min = LR[i][1]
if max <= min:
    print(min - max + 1)
else:
    print(0)
### BUGGY CODE ###

H, W , N = map(int,input().split())
from bisect import bisect_left
from bisect import bisect_right
matrix = []
for _ in range(N):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    matrix.append([x,y])
matrix.sort()
ans = [0 for _ in range(10)]
from bisect import bisect_left
cand = {}
for l in matrix:
    for x_r in [-2, -1 , 0]:
        for y_r in [-2, -1 , 0]:
            nowx = l[0] + x_r
            nowy = l[1] + y_r
            if nowx < 0 or nowy < 0 or nowx + 2>= H or nowy+ 2 >= W:
                continue
            #ここで起点(左上)nowx, nowy として　 9マスに着目する
            name = str(nowx) + str(nowy)
            try: cand[name] += 1
            except: cand[name] = 1
tmp = ((H - 2) * (W - 2))
for x in cand.values():
    if x > 9:
        while True:
            print(W)
    ans[x] += 1
    tmp -= 1
ans[0] = tmp
for x in ans:
    print(x)

    
    


### FIXED CODE ###

H, W , N = map(int,input().split())
from bisect import bisect_left
from bisect import bisect_right
matrix = []
for _ in range(N):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    matrix.append([x,y])
matrix.sort()
ans = [0 for _ in range(10)]
cand = {}
for l in matrix:
    for x_r in [-2, -1 , 0]:
        for y_r in [-2, -1 , 0]:
            nowx = l[0] + x_r
            nowy = l[1] + y_r
            if nowx < 0 or nowy < 0 or nowx + 2>= H or nowy+ 2 >= W:
                continue
            #ここで起点(左上)nowx, nowy として　 9マスに着目する
            name = str(nowx) +"hoge" +str(nowy)
            try: cand[name] += 1
            except: cand[name] = 1
tmp = ((H - 2) * (W - 2))
for x in cand.values():
    ans[x] += 1
    tmp -= 1
ans[0] = tmp
for x in ans:
    print(x)
### BUGGY CODE ###

import collections
import bisect

n = int(input())
s = [input() for i in range(n)]

c = collections.Counter(s)
values,counts = zip(*c.most_common())
max_w = counts[0]
l = len(counts)

ans_list = []
i = 0
while True:
    if i < l:
        if counts[i] == max_w:
            bisect.insort(ans_list,values[i])
    else:
        break
    i += 1 

for j in ans_list:
    print(j)

### FIXED CODE ###

n = int(input())
d = dict()

for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

M = max(d.values())

ans_list = []
for k,v in d.items():
    if v == M:
        ans_list.append(k)

ans_list.sort()
for i in ans_list:
    print(i)
### BUGGY CODE ###

#!/usr/bin/python
#coding: utf-8

N, K = map(int, raw_input().split())
l = map(int, raw_input().split())

s = list(set(l))
num = range(len(s))
if len(s) <= K: print 0
else:
    for i in range(len(s)):
        num[i] = len([j for j in l if j == s[i]])
    sousa = len(s)-K
    num.sort()
    print sum(num[:sousa])


### FIXED CODE ###

#!/usr/bin/python
#coding: utf-8

from collections import Counter

N, K = map(int, raw_input().split())
l = map(int, raw_input().split())

s = list(set(l))
num = range(len(s))
if len(s) <= K: print 0
else:
    counter = Counter(l)
    nums = counter.values()
    sousa = len(s)-K
    nums.sort()
    print sum(nums[:sousa])
### BUGGY CODE ###

l,r = map(int,input().split())
min = 20000
for i in range(l,r,1):
    for j in range(l+1,r+1,1):
        if min >= (i*j)%2019:
            min = (i*j)%2019
print(min)

### FIXED CODE ###

l,r = map(int,input().split())
ans = 2019
if r-l+1 >= 2019:
    print(0)
else:
    for i in range(l,r):
        for j in range(i+1,r+1):
            ans = min( (i*j) % 2019, ans)
    print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
_a = a[:]
_a.sort()
__a = a[:]
__a.sort(reverse=True)

i = 0
cand_1 = [_a.pop(-1)]
cand_2 = [__a.pop(-1)]
while len(_a) > 0:
    if i % 4 < 2:
        _b = _a.pop(0)
        __b = __a.pop(0)
    else:
        _b = _a.pop(-1)
        __b = __a.pop(-1)
    if i % 2 == 0:
        cand_1.append(_b)
        cand_2.append(__b)
    else:
        cand_1.insert(0, _b)
        cand_2.insert(0, __b)
    i += 1
res1 = 0
res2 = 0
for i in range(1, n):
    res1+= abs(cand_1[i]-cand_1[i-1])
    res2+= abs(cand_2[i]-cand_2[i-1])

print(max(res1, res2))


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a.sort(reverse=True)

if n % 2 == 0:
    res = 0
    for i in range(n // 2 - 1):
        res += a[i] * 2
    res += a[n // 2 - 1]
    res -= a[n // 2]
    for i in range(n // 2 + 1, n):
        res -= a[i] * 2
    print(res)
else:
    res1 = 0
    for i in range(n // 2 - 1):
        res1 += a[i] * 2
    res1 += a[n // 2 - 1] + a[n // 2]
    for i in range(n // 2 + 1, n):
        res1 -= a[i] * 2

    res2 = 0
    for i in range(n // 2):
        res2 += a[i] * 2
    res2 -= a[n // 2] + a[n // 2 + 1]
    for i in range(n // 2 + 2, n):
        res2 -= a[i] * 2
    print(max(res1, res2))
### BUGGY CODE ###

import re
 
n, q = map(int, input().split())
s = input()
 
l = []
r = []
 
for i in range(q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)

for i in range(q):
    m = re.findall("AC", s[l[i] - 1 : r[i]])
    print(len(m))

### FIXED CODE ###

import re
 
n, q = map(int, input().split())
s = input()
 
l = []
r = []
 
for i in range(q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
 
memo = [0 for i in range(len(s))]
cnt = 0
 
for i in range(1, len(s)):
    if s[i - 1] == "A" and s[i] == "C":
        cnt += 1
    memo[i] = cnt
 
for i in range(q):
    print(memo[r[i] - 1] - memo[l[i] - 1])
### BUGGY CODE ###

S = list(input())
ans = 0
for _ in range(len(S)):
    check = S[0]
    tmp = ans
    for i in range(1,len(S)):
        if check != S[i]:
            ans += 2
            del S[i-1:i+1]
            break
        check = S[i]
    if len(S) == 0:
        break
    if tmp == ans:
        break
print(ans)

### FIXED CODE ###

S = list(input())
c0 = 0
c1 = 0
for i in S:
    if i == '0':
        c0 += 1
    else:
        c1 += 1
ans = min(c0,c1) * 2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
        self.revE = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        self.revE[t].append((s, w))


def solve(N: int, M: int, s: "List[int]", t: "List[int]"):
    c = Counter(s)
    g = Graph(N)
    for ss, tt in zip(s, t):
        g.add_edge(ss, tt)

    DP = [0]*N
    for i in range(N-2, -1, -1):
        DP[i] = sum(DP[t] for t, w in g.E[i])/c[i] + 1

    gm = DP[0]
    for i in range(N-2):
        if len(g.E[i]) == 1:
            continue
        dp = DP[:]
        for j in range(i, -1, -1):
            a = tuple(dp[t] for t, w in g.E[j])
            b = sum(a)
            if i == j:
                dp[j] = (b-max(a))/(c[j]-1)
            else:
                dp[j] = b/c[j]
            dp[j] += 1
        gm = min(dp[0], gm)
        # print(dp)
    print(gm)


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    s = [int()] * (M)  # type: "List[int]"
    t = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        s[i] = int(next(tokens))-1
        t[i] = int(next(tokens))-1
    solve(N, M, s, t)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append(t)


def solve(N: int, M: int, s: "List[int]", t: "List[int]"):
    c = Counter(s)
    g = Graph(N)
    for ss, tt in zip(s, t):
        g.add_edge(ss, tt)

    DP = [0]*N
    for i in range(N-2, -1, -1):
        DP[i] = sum(DP[t] for t in g.E[i])/c[i] + 1

    gm = DP[0]
    for i in range(N-2):
        if len(g.E[i]) == 1:
            continue
        dp = DP[:]
        for j in range(i, -1, -1):
            tot, m = 0, 0
            for t in g.E[j]:
                tot += dp[t]
                m = max(dp[t], m)
            if i == j:
                dp[j] = (tot-m)/(c[j]-1)
            else:
                dp[j] = tot/c[j]
            dp[j] += 1
        gm = min(dp[0], gm)
        # print(dp)
    print(gm)


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    s = [int()] * (M)  # type: "List[int]"
    t = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        s[i] = int(next(tokens))-1
        t[i] = int(next(tokens))-1
    solve(N, M, s, t)


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

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = lambda: stdin.readline().strip()

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()


### FIXED CODE ###

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()
### BUGGY CODE ###

n = int(input())
d = list(map(lambda x: int(x), input().split()))

res = 0


def is_triangle(i, j, k):
    return 1 if i < j + k and j < i + k and k < i + j else 0


i = 0
j = 1
k = 2

while i < n:
    while j < n:
        while k < n:
            res += is_triangle(d[i],d[j],d[k])
            k += 1
        j += 1
        k = j + 1
    i += 1
    j = i + 1
    k = j + 1


print(res)

### FIXED CODE ###

n = int(input())
d = list(map(lambda x: int(x), input().split()))
d.sort()

res = 0

for i in range(n-2):
    k = i + 2
    for j in range(i+1, n-1):
        while k < n and d[i] + d[j] > d[k]:
            k += 1
        if k > j:
            res += k - j - 1

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

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

P = []

for i in range(N):
    temp = A.index(i+1) + 1
    print(temp,end=' ')
#    temp = str(temp)
#    P.append(temp)


#print(' '.join(P))


### FIXED CODE ###

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

P = ['']*N

for i in range(N):
    P[A[i]-1] = str(i + 1)


print(' '.join(P))
### BUGGY CODE ###

import numpy as np

def resolve():
    n, w = map(int, input().split())
    goods = np.array([list(map(int, input().split())) for _ in range(n)])

    dp = np.ndarray((n, w))
    dp.fill(-1)

    print(knapsack(n - 1, w, goods, dp))

def knapsack(i, j, goods, dp):
    """残りi個の品物から、重さがj以下になるように選んだときの価値の最大値をreturnする関数"""
    if i < 0:
        # もう品物は残っていない
        res = 0

    elif dp[i - 1, j - 1] != -1:
        return dp[i - 1, j - 1]

    elif j < goods[i][0]:
        # 品物が重すぎて入らない
        res = knapsack(i - 1, j, goods, dp)
        dp[i - 1, j - 1] = res
    else:
        # 品物を入れる場合と入れない場合とで、価値が大きい方をreturn
        res = max(knapsack(i - 1, j - goods[i][0], goods, dp) + goods[i][1], knapsack(i - 1, j, goods, dp))
        dp[i - 1, j - 1] = res

    return res
  
resolve()

### FIXED CODE ###

def resolve():
    n, w = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0] * (w + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in reversed(range(w + 1)):
            # もしi番目の品物が入るのであれば
            if goods[i - 1][0] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[n][w])
    
resolve()
### BUGGY CODE ###

def main():
  _range = range
  h, w = map(int, input().split())
  s = [input() + '#' for _ in _range(h)]
  s.append('#' * (w + 1))
  t = [[-1] * w for _ in _range(h + 1)]
  tstart = [-1] * (w + 1)
  for i in _range(h + 1):
    ystart = -1
    si = s[i]
    ti = t[i]
    for j in _range(w + 1):
      if si[j] == '#':
        if ystart != -1:
          for k in _range(ystart, j):
            ti[k] += j - ystart
          ystart = -1
        if tstart[j] != -1:
          for k in _range(tstart[j], i):
            t[k][j] += i - tstart[j]
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tstart[j] == -1:
          tstart[j] = i
  print(max(map(max, t)))
main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

N= int(input())
A = list(map(int, input().split()))
C=0
for i in range(N):
    C += A.count(i+1) * (A.count(i+1) - 1) / 2
for i in range(N):
    print(int(C-(A.count(A[i]))+1))

### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))
### BUGGY CODE ###

import sys,collections,math
input = sys.stdin.readline

n,a,b = list(map(int,input().split()))
m = 10**9+7
ans = pow(2,n,m)


la  = 1
laa = 1
for i in range(n,n-a,-1):
    la = la*i
for i in range(1,a+1):
    laa = laa*i

lb  = 1
lbb = 1
for i in range(n,n-b,-1):
    lb = lb*i
for i in range(1,b+1):
    lbb = lbb*i

la = (la*pow(laa,10**9+5,m))%m
lb = (lb*pow(lbb,10**9+5,m))%m

print((ans-la-lb-1)%m)


### FIXED CODE ###

import sys,collections,math
input = sys.stdin.readline

n,a,b = list(map(int,input().split()))
m = 10**9+7
ans = pow(2,n,m)


la  = 1
laa = 1
for i in range(n,n-a,-1):
    la = (la*i)%m
for i in range(1,a+1):
    laa = (laa*i)%m

lb  = 1
lbb = 1
for i in range(n,n-b,-1):
    lb = (lb*i)%m
for i in range(1,b+1):
    lbb = (lbb*i)%m

la = (la*pow(laa,10**9+5,m))%m
lb = (lb*pow(lbb,10**9+5,m))%m

print((ans-la-lb-1)%m)
### BUGGY CODE ###

[X,K,D] = input().split()
X = int(X)
K = int(K)
D = int(D)
c = 0

while c < K :
    if c == 0 :
        NX = X
        OX = NX
    if abs(NX + D) < abs(NX - D) :
        NX = NX + D
    else :
        NX = NX - D
    if abs(OX) > abs(NX) :
        OX = NX
        c = c + 1
    else:
        break

if (K - c) % 2 == 1 :
    if abs(OX + D) < abs(OX - D) :
        OX = OX + D
    else:
        OX = OX - D


print(abs(OX))

### FIXED CODE ###

import math
[X,K,D] = input().split()
X = int(X)
K = int(K)
D = int(D)
c = 0
N = min(math.floor(abs(X)/D),K)
if abs(abs(X) - N*D) > abs(abs(X) - (N-1)*D) :
    N = N - 1
if abs(X - N*D) < abs(X + N*D):
    Z = X - N*D
else:
    Z = X + N*D

if (K - N) % 2 == 1 :
    if abs(Z + D) < abs(Z - D) :
        Z = Z + D
    else:
        Z = Z - D


print(abs(Z))
### BUGGY CODE ###

import bisect
n = int(input())
L = [int(input())]
ans = 0
for i in range(1,n):
    t = int(input())
    k = bisect.bisect_left(L, t)
    if k == 0:
        L.append(t)
    else:
        L[k-1] = t
    L.sort()
print(len(L))


### FIXED CODE ###

from collections import deque
import bisect
n = int(input())
L = deque([int(input())])
for i in range(1,n):
    t = int(input())
    k = bisect.bisect_left(L, t)
    if k == 0:
        L.appendleft(t)
    else:
        L[k-1] = t
print(len(L))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
ans = 0
for i in range(a,b+1):
    if i%c != 0 and i%d != 0 :
        ans += 1

print(ans)


### FIXED CODE ###

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

import math

bc = b//c
bd = b//d
bcd = b//(c*d//math.gcd(c,d))

ac = (a-1)//c
ad = (a-1)//d
acd = (a-1)//(c*d//math.gcd(c,d))

ans = (b-bc-bd+bcd)-((a-1)-ac-ad+acd)

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

import sys
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    sy -= 1
    sx -= 1
    gx -= 1
    gy -=1
    lake = [list(readline().decode('utf-8').strip()) for _ in range(H)]
    dist = [[INF] * W for _ in range(H)]
    dxy = ((1, 0), (0, 1), (-1, 0), (0, -1))
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if (y,x) == (gy, gx):
            print(d)
            sys.exit()
        for dx,dy in dxy:
            n_y = y
            n_x = x
            for _ in range(K):
                n_y +=dy
                n_x +=dx

                if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                    if dist[n_y][n_x]<d:
                        break
                    elif dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

import sys

K = int(input())

seven = 7
for i in range(10**6):
    if seven % K == 0:
        print(i+1)
        sys.exit()
    else:
        seven = seven * 10 + 7

print(-1)


### FIXED CODE ###

import sys

K = int(input())

seven = 7
mod = 7 % K
for i in range(10**6):
    seven = seven % K
    if seven == 0:
        print(i+1)
        sys.exit()
    else:
        seven = seven * (10 % K) + mod

print(-1)