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

import numpy as np
N,K = map(int, input().split())

A_list = np.array([0]+list(map(int, input().split())))
#print(A_np)


for j in range(K):
  new_A=np.zeros(N+2,dtype=np.int64)
  for i in range(1,N+1):
    #print(new_A)
    mi=i-A_list[i]
    ma=i+A_list[i]
    if mi<0:
      mi=0
    if ma>N:
      ma=N
    #new_A[mi:ma+1]+=1
    new_A[mi]+=1
    new_A[ma+1]-=1

  A_list=np.cumsum(new_A)
  if sum(A_list[1:N+1])==N*N:
    break
    
for i in range(1,N+1):
  print(A_list[i],end=" ")


### FIXED CODE ###

import numpy as np
from numba import njit

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")
### BUGGY CODE ###

import math
ans = 0
k = int(input())

for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            gcd_1 = math.gcd(i,j)
            gcd_2 = math.gcd(gcd_1,k)
            ans += gcd_2
print(ans)

### FIXED CODE ###

from math import gcd
ans = 0
k = int(input())
 
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += gcd(k,gcd(i,j))

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

n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
for i in range(m):
    l[-1] = l[-1]//2
    l.sort()
print(sum(l))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
l = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(l)
for i in range(m):
    min = heapq.heappop(l)
    heapq.heappush(l,(-1)*(-min//2))
    
print(-sum(l))
### BUGGY CODE ###

def sigma(n):
    a = 0
    for i in range(1, n + 1):
        a += i
    return a


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    a = []
    for p in P:
        a.append(sigma(p) / p)

    ans = 0
    for i in range(N - K + 1):
        ans = max(ans, sum(a[i : i + K]))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = [(v + 1) / 2 for v in map(int, input().split())]

    ans = tmp = sum(P[0:K])
    for i in range(N - K):
        tmp = tmp - P[i] + P[i + K]
        ans = max(ans, tmp)

    print(ans)


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

def gcd(g1, g2):
    x = min(g1, g2)
    y = max(g1, g2)

    if y % x == 0:
        return x
    else:
        return gcd(x, y % x)


def prime_factorize(n):
    p = []
    while n % 2 == 0:
        if 2 not in p:
            p.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in p:
                p.append(f)
                n //= f
        else:
            f += 2
    if n != 1 and n not in p:
        p.append(n)
    return p


a, b = map(int, input().split())
q = prime_factorize(gcd(a, b))
# print(q)
print(len(q) + 1)


### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


def prime_factorize(n):
    p = []
    while n % 2 == 0:
        if 2 not in p:
            p.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in p:
                p.append(f)
            n //= f
        else:
            f += 2
    if n != 1 and n not in p:
        p.append(n)
    return p


a, b = map(int, input().split())
q = prime_factorize(gcd(a, b))
# print(q)
print(len(q) + 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0

for i in range(n):
    for j in range(i + 1, n):
        s += a[i] * a[j]

print(s % (10 ** 9 + 7))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a_sum = 0
s = []
ans = 0

for i in range(n):
    a_sum += a[i]
    s.append(a_sum)

for i, j in enumerate(a):
    ans += j * (s[n - 1] - s[i])

print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

def counter(list_1,list_2,length):
    w = list_1.pop()
    count = 0
    while True:
        for x,y in list_2:
            if x == w:
                if not list_1:
                    return count * length + y
                w = list_1.pop()
        count += 1
s = input()
le_s = len(s)
t = input()
l_t = [x for x in t]
l_t.reverse()
s_t = set(l_t)
l_s = []
s_s =set()
i = 1
for y in s:
    if y in s_t:
        l_s.append((y,i))
        s_s.add(y)
    i += 1
if s_t != s_s:
    print(-1)
    exit()
print(counter(l_t,l_s,le_s))


### FIXED CODE ###

def counter(list_1,list_2,length):
    count = 0
    m = 0
    for n in list_1:
        if m == length:
            count += 1
            m = 0
        m = list_2[n][m]
        if m == -1 :
            count += 1
            m = list_2[n][0]
    return count * length + m
s = input()
le_s = len(s)
t = input()
l_t = [ord(x)-97 for x in t]
s_t = set(l_t)
l_s = [[-1 for p in range(le_s)] for _ in range(26)]
s_s =set()
i = 1
l_c = [0 for _ in range(26)]
for y in s:
    z = ord(y)-97
    if z in s_t:
        l_s[z][l_c[z]:i] = [i for a in range(i - l_c[z])]
        l_c[z] = i
        s_s.add(z)
    i += 1
if s_t != s_s:
    print(-1)
    exit()
print(counter(l_t,l_s,le_s))
### BUGGY CODE ###

N, M = map(int, input().split())
tmp = input().split(' ')
H = []
for i in range(N):
    H = H + [int(tmp[i])]

A = []
B = []
for i in range(M):
    ta, tb = map(int, input().split())
    A = A + [ta]
    B = B + [tb]

ans = [True]*N
# v: 1ならいい展望台、0なら良くない展望台 
for i in range(M):
    ans[A[i]-1] = H[A[i]-1] > H[B[i]-1] and ans[A[i]-1]
    ans[B[i]-1] = H[B[i]-1] > H[A[i]-1] and ans[B[i]-1]

print(ans.count(True))

### FIXED CODE ###

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

A = [0]*M
B = [0]*M
for i in range(M):
    ta, tb = map(int, input().split())
    A[i] = ta - 1
    B[i] = tb - 1

ans = [True]*N
# v: Trueならいい展望台、Falseなら良くない展望台 
for i in range(M):
    ans[A[i]] = H[A[i]] > H[B[i]] and ans[A[i]]
    ans[B[i]] = H[B[i]] > H[A[i]] and ans[B[i]]

print(ans.count(True))
### BUGGY CODE ###


n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]


edgeset = set()
for i,j in edges:
    edgeset.add((min(i,j),max(i,j)))


def addEdge(graph,u,v):
    graph[u].add(v)


def deleteNode(graph,node):
    graph.pop(node,None)

from collections import defaultdict
graphAB = defaultdict(set)
graphABopp = defaultdict(set)

for i,j in edgeset:
    addEdge(graphAB,i,j)
    addEdge(graphABopp,j,i)



def adjAB(node):
    Aflag = False
    Bflag = False
    for i in graphAB[node]:
        if s[i-1] == 'A':
            Aflag = True
        if s[i-1] == 'B':
            Bflag = True
        if Aflag and Bflag:
            break
    for i in graphABopp[node]:
        if s[i-1] == 'A':
            Aflag = True
        if s[i-1] == 'B':
            Bflag = True
        if Aflag and Bflag:
            break
    if Aflag and Bflag:
        return(True)
    else:
        return(False)



visitset = set([i for i in set(graphAB.keys())|set(graphABopp.keys()) if not adjAB(i)])
deleteset = set()
#print(visitset)

while bool(visitset):
    i = visitset.pop()
    deleteset.add(i)
    for j in graphAB[i]:
        graphABopp[j].remove(i)
        if not adjAB(j):
            visitset.add(j)
            #print(visitset,'add')
    for j in graphABopp[i]:
        graphAB[j].remove(i)
        if not adjAB(j):
            visitset.add(j)
            #print(visitset,'add')
    graphAB.pop(i,None)
    graphABopp.pop(i,None)

#print(graphAB)
#print(graphABopp)


if graphAB == {} and graphABopp == {}:
    print('No')
else:
    print('Yes')





### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].add(v)


from collections import defaultdict
graphAB = defaultdict(set)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'

#print(graphAB)
#print(graphABopp)

sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def solve():
    N = int(raw_input())
    Di = []
    sum = 0
    for i in range(N):
        di = int(raw_input())
        sum += di
        Di.append((di, i))
    if sum % 2 > 0:
        print '-1'
        return
    Di.sort(key = lambda x : x[0] ,reverse = True)
    d_to_i = {dd:i for dd, i in Di}
    # child = [[] for i in range(N)]
    ans = []
    n_child = [1] * N
    d_child = [0] * N
    for valD, node in Di:
        valD_par = valD - N + 2 * n_child[node]
        if valD_par in d_to_i.keys():
            node_par = d_to_i[valD_par]
            # child[node].append(node_par) ##
            # child[node_par].append(node)
            ans.append([node_par + 1, node + 1])
            n_child[node_par] += n_child[node]
            d_child[node_par] += n_child[node] + d_child[node]
            if n_child[node_par] == N:
                break
        else:
            print '-1'
            return
    # check if Di satisfied or not
    d_min, i_min = Di[-1]
    if d_child[i_min] != d_min:
        print '-1'
        return
    # for i in range(N):
    #     for j in child[i]:
    #         print str(i + 1) + ' ' + str(j + 1)
    for ele in ans:
        print str(ele[0]) + ' ' + str(ele[1])

if __name__ == '__main__':
    solve()


### FIXED CODE ###

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

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)
### BUGGY CODE ###

from collections import Counter

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    ans = sum(a)
    q = int(input())
    d = dict((x,a.count(x)) for x in set(a))
    # Counterを敢えて使わないでやってみる
    # d = Counter(a)
    for _ in range(q):
        b, c = map(int, input().split())
        # cの値がない場合の対処
        d.setdefault(c, 0)
        # bの値がない場合の対処
        d[c] = d.get(c) + d.get(b, 0)
        # 差分はbの個数 * (c-b) 
        diff = d.get(b, 0) * (c-b)
        d[b] = 0
        ans += diff
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    ans = sum(a)
    q = int(input())
    #d = dict((x,a.count(x)) for x in set(a))
    d = Counter(a)
    for _ in range(q):
        b, c = map(int, input().split())
        # cの値がない場合の対処
        d.setdefault(c, 0)
        # bの値がない場合の対処
        d[c] = d.get(c) + d.get(b, 0)
        # 差分はbの個数 * (c-b) 
        diff = d.get(b, 0) * (c-b)
        d[b] = 0
        ans += diff
        print(ans)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

count=0
for i in range(N):
    flag=True
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            flag=False
    if flag==True:
        count+=1
        
print(count)

### FIXED CODE ###

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

dp=[0]*(max(A)+1)

for a in A:
    for x in range(a,len(dp),a):
        dp[x]+=1

count=0
for a in A:
    if dp[a]==1:
        count+=1

print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
ans = 0


for i in range(n):
    a = k * (i+1)
    if a <= n:
        for ii in range(n):
            b = k * (ii+1)
            if b <= n:
                for iii in range(n):
                    c = k * (iii+1)
                    if c <= n:
                        ans = ans + 1
                        #print(a,b,c)
                    else:
                        break
            else:
                break
    else:
        break


if k % 2 == 0:
    for j in range(n):
        a = int(k/2) + k * j
        if a <= n:
            for jj in range(n):
                b = int(k/2) + k * jj
                if b <= n:
                    for jjj in range(n):
                        c = int(k/2) + k * jjj
                        if c <= n:
                            ans = ans + 1
                            #print(a,b,c)
                        else:
                            break
                else:
                    break
        else:
            break

print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
ans = 0

if k % 2 != 0:
    print((n//k)**3)
else:
    print((n//k)**3+((n+int(k/2))//k)**3)
### BUGGY CODE ###

X = int(input())
def price(n):
  if n == 1:
    return False
  for i in range(2, int(n**0.5)+1):
    if n%i == 0:
      return False
  return True

while 1:
  if price(X):
    print(X)
  else:
    X += 1

### FIXED CODE ###

X = int(input())
def price(n):
  if n == 1:
    return False
  for i in range(2, int(n**0.5)+1):
    if n%i == 0:
      return False
  return True

while(1):
  if price(X):
    print(X)
    break
  else:
    X += 1
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

dic = {}
for i in range(26):
    dic[chr(i+97)] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[chr(i+97)].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y = int(y) - 1
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[chr(i+97)][bisect_left(dic[chr(i+97)], y)]
            if p <= z:
                res += 1
        print(res)
### BUGGY CODE ###

N,M = map(int,input().split())
pref = [[] for i in range(N)]
id = [[]] * M

for i in range(M):
  p,y = map(int,input().split())
  id[i] = [p,y]
  pref[p - 1].append(y)
  pref[p - 1] = sorted(pref[p - 1])

for i in range(M):
  p = id[i][0]
  y = id[i][1]
  order = str(pref[p -  1].index(y) + 1)
  city = str(p)
  ID = ""
  ID += "0" * (6 - len(city)) + city + "0" * (6 - len(order)) + order
  print(ID)


### FIXED CODE ###

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

L = [list(map(int,input().split())) for i in range(M)]

for i in range(M):
  L[i].append(i + 1)

sortL = sorted(L)

ID = ""

order = 0

for i in range(0,len(L)):
  if sortL[i][0] > sortL[i-1][0]:
    order = 0
  order += 1
  pref = str(sortL[i][0])
  ID = "0" *  (6 - len(pref))
  ID += pref
  ID += "0" * (6 - len(str(order)))
  ID += str(order)
  sortL[i].append(ID)

sortL.sort(key=lambda x: x[2])

for i in range(0,len(L)):
  print(sortL[i][-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from functools import reduce
import fractions


def gcd(*numbers):
  return reduce(fractions.gcd, numbers)


n = int(input())
lst = list(map(int, input().split()))
lst.sort()

max_gcd = 0
for i in reversed(range(n)):
  arr = lst[:i] + lst[i + 1:len(lst)]
  if min(arr) < max_gcd:
    break
  wk_gcd = gcd(*arr)
  max_gcd = wk_gcd if wk_gcd > max_gcd else max_gcd

print(max_gcd)


### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())
a = list(map(int, input().split()))

# 累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
  left[i + 1] = (fractions.gcd(left[i], a[i]))
  right[n - i - 1] = (fractions.gcd(right[n - i], a[n - 1 - i]))

ans = 0
for i in range(n):
  ans = max(ans, fractions.gcd(left[i], right[i + 1]))
print(ans)
### BUGGY CODE ###

import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=0
r=n
while l!=r:
    i=(l+r)//2
    ta = a[i]
    na = a[:i]+a[i+1:]
    dp = [False for _ in range(k+1)]
    dp[0]=True
    for j in range(n-1):
        for m in range(k,0,-1):
            if m-na[j]>=0:
                dp[m]=dp[m] or dp[m-na[j]]
    flag = False
    if ta>=k:flag=True
    else:
        for j in range(k-ta,k):
            if dp[j]:
                flag = True
                break
    if flag:
        r=i
    else:
        l=i+1
print(l)



### FIXED CODE ###

import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a_new = sorted(a)
answer = []
for j in range(1,n+1):
  answer.append(a.index(j)+1)
print(*answer)


### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
answer = np.argsort(a) +1
print(*answer)
### BUGGY CODE ###

def main():
    s = input().strip()
    t = input().strip()
    dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + s[i-1]
            if len(dp[i][j]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j]
            if len(dp[i][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1]
    print(dp[len(s)][len(t)])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s = input().strip()
    t = input().strip()
    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            if dp[i][j] < dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans
    print(ans)


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

def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

X = [0] + [-10**9] * N

for i in range(1, N+1):
    for b in B:
        if b[1] <= i:
            if X[i-b[1]] == 0:
                X[i] = max(X[i], b[0])
            else:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
    
print(X[N])

### FIXED CODE ###

def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]



best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

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

from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                    depth[ny][nx] = depth[y][x] +1
                    dq.append((nx,ny))
            else:
                break
            K -= 1
print(depth[c][d] if depth[c][d] != float("inf") else -1)

### FIXED CODE ###

from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            K -= 1
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                if depth[ny][nx] == depth[y][x]+1:
                    continue
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
            else:
                break
print(depth[c][d] if depth[c][d] != float("inf") else -1)