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

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get_0(self, index):
        s = self.one
        j = index // self.k

        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def get(self, index1, index2):
        s = self.one
        j1 = index1 // self.k
        j2 = index2 // self.k

        if j1 == j2:
            s = self.one
            for i in range(index1, index2 + 1):
                s = self.func(s, self.a[i])
            return s

        for i in range(index1, j1 * self.k + self.k):
            s = self.func(s, self.a[i])
        for i in range(j1+1, j2):
            s = self.func(s, self.b[i])
        for i in range(j2 * self.k, index2 + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(0, h[i])
    buc.update(h[i], j + a[i])

print(buc.get(0, n))


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)
dic = []
for i in range(1, n + 1):
    for j in range(0, n - i + 1):
        if s[j:j+i] not in dic:
            dic.append(s[j:j+i])
dic.sort()
print(dic[k-1])


### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
dic = []
for i in range(n):
    for j in range(1, k + 1):
        if i + j > n:
            break
        if s[i:i+j] not in dic:
            dic.append(s[i:i+j])
dic.sort()
print(dic[k-1])
### BUGGY CODE ###

S = input()
Q = int(input())

jun = True

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun

    if T[0] == "2" and ((T[1] == "1" and jun) or (T[1] == "2" and not jun)):
        S = T[2] + S
        continue
        
    if T[0] == "2" and ((T[1] == "2" and jun) or (T[1] == "1" and not jun)):
        S = S + T[2]

if jun:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())

jun = True
head = ""

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            head += T[2]
            continue

        else:
            S += T[2]

if jun:
    print(head[::-1] + S)
else:
    print(S[::-1] + head)
### BUGGY CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1
ans = r * g * b

for i in range(N):
    for j in range(i + 1, N):
        x = j + j - i
        if S[i] != S[j] and x <= N - 1:
            if S[i] != S[x] and S[x] != S[j]:
                ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            x = 2 * j - i
            if x < N and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

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

import itertools

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

ans = float('inf')
for x, y, z in itertools.permutations(range(C), 3):
    point = 0
    for i, j in itertools.product(range(N), repeat=2):
        if (i + j) % 3 == 0: point += D[c[i][j] - 1][x]
        if (i + j) % 3 == 1: point += D[c[i][j] - 1][y]
        if (i + j) % 3 == 2: point += D[c[i][j] - 1][z]
    ans = min(ans, point)

print(ans)


### FIXED CODE ###

import itertools

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [[int(s) - 1 for s in input().split()] for _ in range(N)]

m0 = [0] * C
m1 = [0] * C
m2 = [0] * C
for i, j in itertools.product(range(N), repeat=2):
    if (i + j) % 3 == 0: m0[c[i][j]] += 1
    if (i + j) % 3 == 1: m1[c[i][j]] += 1
    if (i + j) % 3 == 2: m2[c[i][j]] += 1

ans = float('inf')
for x, y, z in itertools.permutations(range(C), 3):
    point = 0
    for i in range(C): point += D[i][x] * m0[i]
    for i in range(C): point += D[i][y] * m1[i]
    for i in range(C): point += D[i][z] * m2[i]
    ans = min(ans, point)

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

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

B = [0]*N
for i, a in enumerate(A):
    bottom = i-a
    top = i+a+1
    if bottom < 0:
        bottom = 0
    if top > N:
        top = N
    B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))

for _ in range(K):
    A = B[:]
    B = [0]*N
    for i, a in enumerate(A):
        bottom = i-a
        top = i+a+1
        if bottom < 0:
            bottom = 0
        if top > N:
            top = N
        B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))

A = list(map(str, A))
ans = ' '.join(A)
print(ans)


### FIXED CODE ###

from numba import jit
import sys
input = sys.stdin.readline


@jit
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            B[max(0, i-a)] += 1
            B[min(N, i+a+1)] -= 1
        for j in range(1, N):
            B[j] += B[j-1]
        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


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

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]

	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])

solver()

### FIXED CODE ###

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]
 
	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])
 
solver()
### BUGGY CODE ###

def valid_check(n, a, b, c, d, s):
    if not two_rocks(s[b:d]):
        return 0
    if c < d:
        return two_rocks(s[a:c])
    else:
        for possibility in enumerate_possibilities(b, d, s):
            if two_rocks(possibility[a:c]):
                return 1
        return 0



def enumerate_possibilities(b, d, s):
    possibilities = []
    for i in range(d-b+1):
        if s[b+i]=='.':
            tmp = s.copy()
            tmp[b+i] = '#'
            possibilities.append(tmp)
    return possibilities


def two_rocks(s):
    for i in range(len(s)-1):
        if s[i]=='#' and s[i+1]=='#':
            return 0
    return 1

n, a, b, c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = list(input())


if valid_check(n, a, b, c, d, s):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

def valid_check(n, a, b, c, d, s):
    if not two_rocks(s[b:d]):
        return 0
    # if not two_rocks()
    if c < d:
        return two_rocks(s[a:c])
    else:
        return three_spaces(s[b-1:d+2]) and two_rocks(s[a:c])


def three_spaces(s):
    for i in range(len(s)-2):
        if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
            return 1
    return 0

# def enumerate_possibilities(b, d, s):
#     possibilities = []
#     for i in range(d-b+1):
#         if s[b+i]=='.':
#             tmp = s.copy()
#             tmp[b+i] = '#'
#             possibilities.append(tmp)
#     return possibilities


def two_rocks(s):
    for i in range(len(s)-1):
        if s[i]=='#' and s[i+1]=='#':
            return 0
    return 1

n, a, b, c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = list(input())


if valid_check(n, a, b, c, d, s):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

Input = map(int,raw_input().split(' '))
N = Input[0]
K = Input[1]
A = map(int,raw_input().split(' '))
#A = sorted(A)

count = []
for n in range(1,N+1):
	count.append(A.count(n))

count = sorted(count)
zeroCount = count.count(0)
rslt = 0
if zeroCount > N - K :
	print rslt
else:
	while count.count(0) != N - K:
		rslt += count[zeroCount]
		count[zeroCount] = 0
		zeroCount += 1

	print rslt

### FIXED CODE ###

import bisect
Input = map(int,raw_input().split(' '))
N = Input[0]
K = Input[1]
A = map(int,raw_input().split(' '))
A = sorted(A)
count = []
i = 0
while i < len(A):
	count.append(bisect.bisect_right(A,A[i]) - bisect.bisect_left(A,A[i]))
	i = bisect.bisect_right(A,A[i])
count = sorted(count)
dim = len(count)
rslt = 0
if dim <= K:
	print rslt
else:
	rslt += sum(count[:dim-K])
	print rslt
### BUGGY CODE ###

# -*- coding:utf-8 -*-
def odd(num):
    return True if num%2!=0 else False
n = int(input())
a = list(map(int,input().split()))
b = []
for tmp in range(len(a)):
    if odd(n) == odd(tmp+1):
        if len(b) != 0:
            b.insert(0,a[tmp])
        else:
            b.append(a[tmp])
    else:
        b.append(a[tmp])
b = map(str,b)
print(' '.join(b))

### FIXED CODE ###

# -*- coding:utf-8 -*-
from collections import deque
def odd(num):
    return True if num%2!=0 else False
n = int(input())
a = list(input().split())
b = deque()
for tmp in range(len(a)):
    if odd(n) == odd(tmp+1):
        b.appendleft(a[tmp])
    else:
        b.append(a[tmp])
print(' '.join(b))
### BUGGY CODE ###

import queue

H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]

q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]

while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break

                
print(res)


### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
sy,sx=[int(i)-1 for i in input().split()]
gy,gx=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())

dic=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dic.append((i,j))
    
INF=10**9
vis=[[INF]*W for _ in [0]*H]

q=deque()
q.appendleft((sx,sy))
vis[sy][sx]=0
res=-1
while q:
    x,y=q.popleft()
    if (x,y)==(gx,gy):
        res=vis[y][x]
    for dx,dy in dic:
        nx,ny=x+dx,y+dy
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if vis[ny][nx]>vis[y][x] and c[ny][nx]!='#':
                if dx**2+dy**2<2:
                    vis[ny][nx]=vis[y][x]
                    q.appendleft((nx,ny))
                else:
                    vis[ny][nx]=vis[y][x]+1
                    q.append((nx,ny))
        if res>-1:
            break
    if res>-1:
            break
                
print(res)
### BUGGY CODE ###

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

ans=0
for i2 in range(10):
  for j in range(10):
    for k in range(10):
      s='{}{}{}'.format(i2,j,k)
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==s[0]: 
            isOne=1
        elif isTen==0:
          if S[i]==s[1]: 
            isTen=1
        elif isHundred==0:
          if S[i]==s[2]:
            isHundred=1
            ans+=1
        else:
          break

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
S=list(map(int,S))
ans=0
for s in range(1000):
      A=s//100
      B=(s-A*100)//10
      C=s-A*100-B*10
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==A: 
            isOne=1
        elif isTen==0:
          if S[i]==B: 
            isTen=1
        elif isHundred==0:
          if S[i]==C:
            isHundred=1
            ans+=1
        else:
          break

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

from functools import reduce
N = input()
A = list(map(int, input().split()))
a = 1
if 0 in A:
  print(0)
else:
  a = reduce(lambda x, y:x*y, A)
  if a > 10**18:
      print(-1)
  else:
    print(a)

### FIXED CODE ###

N = input()
A = input().split()
if '0' in A:
  print(0)
else:
  a = 1
  for i in A:
    a *= int(i)
    if a > 10**18:
        print(-1)
        exit()
  else:
    print(a)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()
x = [1] + [0]*(p-1)
ans = 0
u = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = (int(s[i])*10**(n-1-i)+u)%p
    ans += x[u]
    x[u] += 1
print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
x = [1] + [0]*(p-1)
ans = 0
u = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = (int(s[i])*pow(10,n-1-i,p)+u)%p
    ans += x[u]
    x[u] += 1
print(ans)
### BUGGY CODE ###

import math
n, m = map(int, input().split())
now_step = 0
checked_steps = {}
factorial_dict = {}
divide_num = 1000000007 

def count_steps(number):
    global checked_steps
    global factorial_dict
    if(number in checked_steps.keys()):
        return checked_steps[number]
    # count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
    # [1,(a+b)]からa個を選ぶ選び方と同じ
    # 余り残は和・積に関して分割法則が成り立つので1,000,000,007 で割ってもいい
    counter = 0
    for i in range(0, number + 1, 2):
        a = number - i
        b = i // 2
        if((a+b) not in factorial_dict):
            factorial_dict[a+b] = math.factorial(a+b)
        if(a not in factorial_dict):
            factorial_dict[a] = math.factorial(a)
        if(b not in factorial_dict):
            factorial_dict[b] = math.factorial(b)
        counter += factorial_dict[a+b] // (factorial_dict[a] * factorial_dict[b])
    checked_steps[number] = counter % divide_num
    return checked_steps[number]

all_count = 1
for i in range(m):
    a = int(input())
    all_count = (all_count * count_steps(a - 1 - now_step)) % divide_num
    now_step = a + 1
all_count = (all_count * count_steps(n - now_step)) % divide_num
print(all_count % divide_num)

### FIXED CODE ###

n, m = map(int, input().split())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 1
checked_steps = {-1:0, 0:1, 1:1}
divide_num = 1000000007 

for i in range(2, n+1):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    if(a < now_step):
        continue
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = list(input())
TD = [input().split() for _ in range(Q)]
TD = [[t,d] for t, d in TD if t in S]

res = [1]*N
for t, d in TD:
  for i in range(N):
    if t == S[i]:
      if d == "L":
        if i == 0:
          res[i] = 0
          break
        res[i-1] += res[i]
        res[i] = 0
      else:
        if i == N-1:
          res[i] = 0
          break
        res[i+1] += res[i]
        res[i] = 0
print(sum(res))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int,input().split())
S = "0"+input()+"0"
TD = [input().rstrip().split() for _ in range(Q)]
l, r = 0, N+1
for t, d in TD[::-1]:
  if t == S[l] and d == "R":
    l -= 1
  elif t == S[l+1] and d == "L":
    l += 1
  if t == S[r] and d == "L":
    r += 1
  elif t == S[r-1] and d == "R":
    r -= 1
print(max(0, r-l-1))
### BUGGY CODE ###

l,n,*ki=map(int,open(0).read().split())
fmax=rmax=0
fl=[]

for ii in range(n):
    f=0
    x=ki[ii:]
    lx=n-ii
    for i in x[:(lx+1)//2]:
        f+=i*2
    for i in x[(lx+1)//2:]:
        f+=(l-i)*2
    if lx%2:
        sa = x[lx//2]
    else:
        sa = l - x[lx // 2]
    f-=sa
    fl.append(f)

for ii in range(n):
    r=0
    x=ki[:n-ii]
    lx=n-ii
    for i in x[:lx//2]:
        r += i * 2
    for i in x[lx//2:]:
        r+=(l-i)*2
    if lx%2:
        sa = l - x[(lx-1) // 2]
    else:
        sa = x[(lx-1)//2]
    r-=sa
    fl.append(r)

print(max(fl))

### FIXED CODE ###

ln, kn, *ki = map(int, open(0).read().split())
# 順回転
pa = ki[-1]
ky = [pa]
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += ki[kn - ys] * 2 + ln - ki[-(ys // 2)] * 2
    # 要素数が奇数の場合
    else:
        pa += ki[kn - ys] * 2 - ki[-(ys // 2) - 1] + ln - ki[-(ys // 2)]
    ky.append(pa)
    kigu *= -1

# 逆回転
pa = ln - ki[0]
ky.append(pa)
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += (ln-ki[ys - 1]) * 2 - ln + ki[ys // 2 - 1] * 2
    # 要素数が奇数の場合
    else:
        pa += (ln-ki[ys - 1]) * 2+ki[ys//2]-ln+ki[ys//2-1]
    ky.append(pa)
    kigu *= -1

print(max(ky))
### BUGGY CODE ###

n, k, q = map(int, input().split())

arr = [int(k)] * n

for i in range(q):
    q_i = int(input())

    for j in range(len(arr)):
        arr[j] = arr[j] - 1
    arr[q_i - 1] += 1

for go_or_not in arr:
    if go_or_not > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
q_list = [int(input()) for i in range(q)]

arr = [k - q] * n

for q_i in q_list:
    arr[q_i - 1] += 1

for go_or_not in arr:
    if go_or_not > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import defaultdict
import sys

input = sys.stdin.readline

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

d = defaultdict(list)

for i in range(n):
    for j in range(i + 1, min(n, i + n // 2) + 1):
        # [i, j)
        d[s[i:j]].append((i, j))

d = sorted(d.items(), key=lambda x: len(x[0]), reverse=True)

for s, lis in d:
    if len(lis) == 1:
        continue
    r = lis[0][1]
    l = lis[-1][0]
    if r <= l:
        print(len(s))
        exit()
print(0)

# print(*d, sep='\n')


### FIXED CODE ###

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

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

res = 0
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
            # dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
print(res)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
import heapq

n, m, full = map(int, input().split())
edges = [[]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])


def dijkstra(num_of_node, edge, start, limit):
    distance = [float('INF')] * num_of_node
    distance[start] = 0
    todo = []
    heapq.heapify(todo)
    heapq.heappush(todo, [0, start])

    while todo:
        d, node = heapq.heappop(todo)
        if d > limit:
            break
        L_edges[start][node] = 1
        for new_node, cost in edge[node]:
            if distance[new_node] > d + cost:
                distance[new_node] = d + cost
                heapq.heappush(todo, [d+cost, new_node])

            else:
                continue
    return


L_edges = [[float('INF')]*n for _ in range(n)]

for i in range(n):
    dijkstra(n, edges, i, full)

for i in range(n):
    L_edges[i][i] = float('INF')
G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))
### BUGGY CODE ###

import math

K = int(input())


def gcd3(a, b, c):
    d = math.gcd(a, b)
    e = math.gcd(d, c)
    return e


ans = 0
for x in range(1, K + 1, 1):
    for y in range(1, K + 1, 1):
        tmp = list(map(lambda z: gcd3(x, y, z), range(1, K+1, 1)))
        ans = ans + sum(tmp)

print(ans)


### FIXED CODE ###

import math

K = int(input())

ans = 0
for x in range(1, K + 1, 1):
    for y in range(1, K + 1, 1):
        ans = ans + sum(list(map(lambda z: math.gcd(math.gcd(x, y), z), range(1, K+1, 1))))

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

N, K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(K):
  p=[0]*N
  n=[0]*N
  for i in range(N):
    if i-A[i]>0:
      p[i-A[i]]+=1
    else:
      p[0]+=1
    if i+A[i]<N-1:
      n[i+A[i]+1]+=1
  light=0
  Ncount=0
  for i in range(N):
    light=light+p[i]-n[i]
    A[i]=light
    if light==N:
      Ncount+=1
  if Ncount==N:
    out=[N]*N
    print(*out, sep=' ')
    exit()
print(*A, sep=' ')

### FIXED CODE ###

N, K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(K):
  p=[0]*N
  n=[0]*N
  for i in range(N):
    if i-A[i]>0:
      p[i-A[i]]+=1
    else:
      p[0]+=1
    if i+A[i]<N-1:
      n[i+A[i]+1]+=1
  light=0
  Ncount=0
  for i in range(N):
    light=light+p[i]-n[i]
    A[i]=light
    if light==N:
      Ncount+=1
  if Ncount==N:
    out=[N]*N
    print(*out, sep=' ')
    exit()
print(*A, sep=' ')