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

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B
ans = ''
for a in A:
    ans += str(a) + ' '
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
print(*A)
### BUGGY CODE ###

n = int(input())

ans = 1
while(n>0):
    ans*=n
    n -= 1

print(ans%(1000000000+7))

### FIXED CODE ###

n = int(input())

ans = 1
while(n>0):
    ans*=n
    ans = ans%(1000000000+7)
    n -= 1

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

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

for i in range(M):
    b, c = map(int, input().split())
    A.extend([c]*b)
A.sort(reverse=True)
ans = A[:N]
print(sum(ans))

### FIXED CODE ###

import heapq
q = []
N, M = map(int, input().split())
A = (map(int, input().split()))
for a in A:
    heapq.heappush(q, a)

lst = []   
for i in range(M):
    lst.append(list(map(int, input().split())))
lst = sorted(lst, key = lambda x: -x[1])
for i, j in lst:
    for _ in range(i):
        v = heapq.heappop(q)
        if v < j:
            heapq.heappush(q, j)
        else:
            heapq.heappush(q, v)
            break
print(sum(q))
### BUGGY CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())
	tot = 0
	while n:
		n, d = divmod(n, 10)
		tot += d 
	if tot % 9 == 0:
		print("Yes")
	else:
		print("No")
	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = str(int(rl()))
	tot = 0
	for c in n:
		tot += int(c)
	if tot % 9 == 0:
		print("Yes")
	else:
		print("No")

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

def main():
  a = input()
  b = input()
  c = input()
  ab = [False]*17000
  ac = [False]*17000
  bc = [False]*17000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+8500]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+8500]))and(not(ac[j+8500]))and(not(bc[j-i+8500])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
  
main()

### FIXED CODE ###

def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  AB = A+B
  AC = A+C
  for i in range(-AC,AC,1):
    for j in range(-AB,AB,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()
### BUGGY CODE ###

n = int(input())
s = input()
m = n
for i in range(n):
    x = s[:i]
    y = s[i+1:]
    m = min(m, x.count('W')+y.count('E'))
print(m)


### FIXED CODE ###

n = int(input())
s = input()
a, e = 0, s.count("E")
for c in s:
    if c == 'W':
        n = min(n, a+e)
        a += 1
    else:
        e -= 1
        n = min(n, a+e)
print(n)
### BUGGY CODE ###

import math
A,B = map(int, input().split())

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
n = 2
p = []
while x != 1:
  if x % n == 0:
    x /= n
    p.append(n)
  else:
    n += 1
p.append(int(x))
p = list(set(p))
print(len(p))
  
  


### FIXED CODE ###

import math
A,B = map(int, input().split())

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
p = []
tmp = int(math.sqrt(x))+1
for n in range(2,tmp):
  while x % n == 0:
    x /= n
    p.append(n)
p.append(int(x))
p.append(1)
p = list(set(p))
print(len(p))
### BUGGY CODE ###

import sys
from collections import defaultdict
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = defaultdict(int)
h_targets = defaultdict(int)
w_targets = defaultdict(int)

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets[(h, w)] += 1
    h_targets[h] += 1
    w_targets[w] += 1


ans = 0
for h in range(H):
    for w in range(W):
        ret = h_targets[h] + w_targets[w] - targets[(h, w)]
        ans = max(ans, ret)
print(ans)


### FIXED CODE ###

import sys
from collections import Counter
from random import shuffle
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = set()
h_targets = []
w_targets = []

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets.add((h, w))
    h_targets.append(h)
    w_targets.append(w)

h_counter = Counter(h_targets).most_common()
w_counter = Counter(w_targets).most_common()

h_high = h_counter[0][1]
w_high = w_counter[0][1]

h_counter = [[k, v] for k, v in h_counter if v == h_high]
w_counter = [[k, v] for k, v in w_counter if v == w_high]
shuffle(h_counter)
shuffle(w_counter)

highest = h_high + w_high
for hk, hv in h_counter:
    for wk, wv in w_counter:
        if hv + wv < highest:
            break
        if ((hk, wk) not in targets):
            print(highest)
            exit()
print(highest - 1)
### BUGGY CODE ###

n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
for i in range(n-2,-1,-1):
    for j in range(n-1,i,-1):
        if j==n-1:
            if s[j]==s[i]:
                dp[i][j]=1
        else:
            if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
                dp[i][j]=dp[i+1][j+1]+1
            else:
                dp[i][j]=0
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
for i in range(n-2,-1,-1):
    for j in range(n-1,i,-1):
        if j==n-1:
            if s[j]==s[i]:
                dp[i][j]=1
        else:
            if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
                dp[i][j]=dp[i+1][j+1]+1
            else:
                dp[i][j]=0
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

L = A[0]
for a in A:
  L = lcm(a,L)
ans = 0
for a in A:
  #ans += L//a
  ans += L*pow(a,MOD-2,MOD)
  ans %= MOD
print(ans)


### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

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

import numpy as np

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

ret = 0
for i in range(len(p)):
    if (np.array(p[:i]) > p[i]).all():
        ret +=1
print(ret)        

### FIXED CODE ###

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

ret = 0
c_min = 2e5

for i in p:
    if c_min >= i:
        c_min = i
        ret+=1
print(ret)
### BUGGY CODE ###

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

D=[{}for i in range(N+1)]
z=[0 for i in range(N)]
D[0][tuple(z)]=0

L=[]
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=[0 for i in range(N)]
    for j in range(N):
        if j+1 in c:
            d[j]=1
    L.append([d,a])
#print(L)

for i in range(N):
    for j in D[i]:
        #print(D[i][j])
        for k in L:
            d=[]
            for l in range(N):
                if j[l]==0 and k[0][l]==0:
                    d.append(0)
                else:
                    d.append(1)
            #print(d)
            if tuple(d) not in D[sum(d)]:
                D[sum(d)][tuple(d)]=D[i][j]+k[1]
            else:
                if D[sum(d)][tuple(d)]>D[i][j]+k[1]:
                    D[sum(d)][tuple(d)]=D[i][j]+k[1]
ans=[1 for i in range(N)]
if tuple(ans) not in D[N]:
    print(-1)
else:
    print(D[N][tuple(ans)])

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())

L={}
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for j in c:
        d+=2**(N-j)
    if d not in L:
        L[d]=a
    else:
        if L[d]>a:
            L[d]=a
#print(L)

D={}
D[0]=0
C=0
for i in range(N):
    C+=2**(N-1-i)
    E={}
    for j in D:
        for k in L:
            if j>=C:
                if j not in E:
                    E[j]=D[j]
                else:
                    if E[j]>D[j]:
                        E[j]=D[j]
            if j|k>=C:
                if j|k not in E:
                    E[j|k]=D[j]+L[k]
                else:
                    if E[j|k]>D[j]+L[k]:
                        E[j|k]=D[j]+L[k]
    #print(E)
    D=E
if len(D)==0:
    print(-1)
else:
    print(D[2**N-1])
### BUGGY CODE ###

from collections import deque
import copy, sys
 
input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0
 
def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))
 
fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]
 
while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)
 
if all(map(len, a)):
    print(-1)
else:
    print(day)

### FIXED CODE ###

from collections import deque
import copy, sys

input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)
### BUGGY CODE ###

s = input()
t = input()

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

for i in range(len_s+1):
    for j in range(len_t+1):
        if i+1 <= len_s and j+1 <= len_t and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        if i+1 <= len_s and j <= len_t:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if i <= len_s and j+1 <= len_t:
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1

print(ans[::-1])


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * 3010 for _ in range(3010)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len(s)
j = len(t)
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res += s[i-1]
        i -= 1
        j -= 1

ans = ""
for i in reversed(range(len(res))):
    ans += res[i]

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

n=int(input())
a=sorted(list(map(int,input().split())))
ans=[]
for i in range(n):
    for j in range(n):
        if i<j:
            c=a[i]^a[j]
            if a.count(c)>0:
                ans.append(c)
            else:break
ans=sorted(ans)
print("Yes" if ans==a else "No")

### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
LL=list(set(L))
ans="No"
if LL==[0]:
    ans="Yes"
elif len(LL)==2:
    if L.count(LL[0])==2*L.count(LL[1]) or L.count(LL[1])==2*L.count(LL[0]):
        ans="Yes"
elif len(LL)==3:
    if L.count(LL[0])==L.count(LL[1]) and L.count(LL[1])==L.count(LL[2]):
        if LL[0]^LL[1]^LL[2]==0:
            ans="Yes"
print(ans)
### BUGGY CODE ###

n = int(input())
m = 0

for i in range(n-1):
  m += (i+1) % (i+2)
  
print(m)

### FIXED CODE ###

n = int(input())
print(n * (n-1) // 2)
### BUGGY CODE ###

n,m = map(int, input().split())

Answer = [p+1 for p in range(n)]

for i in range(m):
  l,r = map(int, input().split())
  Answer = [q for q in Answer if q >=l and q <= r]
  
print(len(Answer))  

### FIXED CODE ###

n, m = map(int, input().split())

min_value = 1
max_value = n

for _ in range(m):
  l, r = map(int, input().split())
  if l >= min_value:
    min_value = l
  if r <= max_value:
    max_value = r

Answer = max(max_value - min_value +1,0)

print(Answer)
### BUGGY CODE ###

H, W, M = map(int, input().split())
hk = [[0, i] for i in range(H + 1)]
wk = [[0, j] for j in range(W + 1)]
s = set()
for i in range(M):
    h, w = map(int, input().split())
    hk[h][0] += 1
    wk[w][0] += 1
    s.add((h, w))
hk.sort(reverse=True)
wk.sort(reverse=True)
colmax = wk[0][0]
ans = 0
for lowacc, i in hk:
    if lowacc + colmax < ans:
        break
    for colacc, j in wk:
        ans = max(ans, lowacc + colacc - ((i, j) in s))
        if lowacc + colacc < ans:
            break
print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
hk = [[0, i] for i in range(H + 1)]
wk = [[0, j] for j in range(W + 1)]
s = set()
for i in range(M):
    h, w = map(int, input().split())
    hk[h][0] += 1
    wk[w][0] += 1
    s.add((h, w))
hk.sort(reverse=True)
wk.sort(reverse=True)
colmax = wk[0][0]
ans = 0
for lowacc, i in hk:
    if lowacc + colmax <= ans:
        break
    for colacc, j in wk:
        if lowacc + colacc <= ans:
            break
        else:
            ans = max(ans, lowacc + colacc - ((i, j) in s))
print(ans)
### BUGGY CODE ###

N,K=input().split()
n,k=int(N),int(K)
p=list(input().split())

for i in range (len(p)):
    p[i]=int(p[i])


sums=0
maxi=0

for i in range(0,n-k+1):
    sums=0
    for t in range(i,i+k):
        sums=sums+p[t]
    if sums>=maxi:
        maxi=sums
    
print((maxi+k)/2)


### FIXED CODE ###

n, k = list (map (int, input ().split ()))
p = [0] + list (map (int, input ().split ()))
s = [0 for i in range (n + 1)]
mx = 0
tag = 0
f = [0.0 for i in range (n + 1)]
for i in range (1, n + 1) :
    s[i] = s[i - 1] + (p[i] + 1) * p[i] / 2 / p[i]
    if (i >= k and s[i] - s[i - k] > mx) :
        mx = s[i] - s[i - k]
print (mx)
### BUGGY CODE ###

n=int(input())

a=list(map(int,input().split()))
b=[]

for i in range(n):
    b.append(a[i])
    b.reverse()

for i in range(n):
    print(b[i],end=" ")

### FIXED CODE ###

n=int(input())

a=list(map(int,input().split()))
b=[0]*n
cen=n//2
if n%2:#n%2==1
    for i in range(0,n):
        if i%2==1:
            b[cen+(i+1)//2]=a[i]
        else:
            b[cen-(i+1)//2]=a[i]
else:
    for i in range(0,n):
        if i%2==1:
            b[cen-(i+1)//2]=a[i]
        else:
            b[cen+(i+1)//2]=a[i]
"""
for i in range(n):
    b.append(a[i])
    b.reverse()
"""
for i in range(n):
    print(b[i],end=" ")
### BUGGY CODE ###

# coding:utf-8

import copy

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    masu = []
    for i in range(H):
        masu.append(input().rstrip())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]

    steplist = []
    for y in range(H):
        for x in range(W):
            if masu[y][x] == Black:
                memo[y][x] = 0
                count -= 1
                steplist.append([y, x])

    while count > 0:
        temp_step = step
        step += 1
        next_list = []
        for l in steplist:
            y = l[0]
            x = l[1]
            for i in range(4):
                temp_x = x + dir_x[i]
                temp_y = y + dir_y[i]
                if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H and memo[temp_y][temp_x] < 0:
                    memo[temp_y][temp_x] = step
                    count -= 1
                    next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding:utf-8

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]
    steplist = []

    for y in range(H):
        temp_in = input()
        for x in range(W):
            if temp_in[x] == Black:
                memo[y][x] = 0
                count -= 1
                steplist.append([y, x])

    while count > 0:
        step += 1
        next_list = []
        for l_yx in steplist:
            for i in range(4):
                temp_x = l_yx[1] + dir_x[i]
                temp_y = l_yx[0] + dir_y[i]
                if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H:
                    if memo[temp_y][temp_x] < 0:
                        memo[temp_y][temp_x] = step
                        count -= 1
                        next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


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

from collections import deque
from heapq import heappop, heappush

def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = []

    dd = [[-1 for _ in range(w)] for _ in range(h)]
    que1 = deque()
    que1.append((x,y))
    dd[x][y] = 0
    while que1:
        (qx,qy) = que1.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            nx = qx + dx[i]
            ny = qy + dy[i]
            if not(nx>=0 and h>nx and ny>=0 and w>ny):
                continue
            if c[nx][ny] != "@" and dd[nx][ny] == -1:
                dd[nx][ny] = dd[qx][qy] + 1
                que1.append((nx,ny))
    if dd[gx][gy] == -1:
        print(-1)
        return


    heappush(que,(0,(x,y)))
    d[x][y] = 0
    while que:
        [num,(qx,qy)] = heappop(que)
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    heappush(que,[d[nx][ny],(nx,ny)])
    print(d[gx][gy])


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy]+1):
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        inv%=k
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0]*(W+1) for _ in range(N+1)]
ans = 0
for i in range(N):
    for sum_w in range(W + 1):
    	if sum_w - w[i] >= 0:
    		dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i])
    	else:
    		dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
    	ans = max(ans,dp[i+1][sum_w])
print(ans)

### FIXED CODE ###

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

w = []
v = []

for i in range(N):
	a,b = map(int,input().split())
	w.append(a)
	v.append(b)

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
	for sum_w in range(W+1):
		if sum_w - w[i] >=0:
			dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

		dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])
### BUGGY CODE ###

n,k=map(int, input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        s.append(j)
mod=998244353
dp=[0]*n
dp[0]=1
for i in range(1,n):
    for j in s:
        if i-j>=0:
            dp[i]+=dp[i-j]
            dp[i]%=mod
print(dp[-1])

### FIXED CODE ###

n,k=map(int, input().split())
lr=[list(map(int,input().split())) for _ in range(k)]
mod=998244353
dp2=[0]*n
dp2[0]=1
for i in range(1,n):
    dp2[i]+=dp2[i-1]
    for l,r in lr:
        if i-l>=0:
            dp2[i]+=dp2[i-l]
        elif i-l<0 and i-r>=0:
            dp2[i]+=dp2[0]
        if i-r-1>=0:
            dp2[i]-=dp2[i-r-1]
    dp2[i]%=mod
print((dp2[-1]-dp2[-2])%mod)