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

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

s = ns()
ls = len(s)
lk = ni()
dp = [[[0]*(lk+1) for _ in range(ls)] for i in range(ls)]
for i in range(ls):
  dp[i][i][0] = 1
for k in range(lk+1):
  for dis in range(1, ls):
    for i in range(ls - dis):
      j = i + dis
      if s[i] == s[j]:
        dp[i][j][k] = dp[i+1][j-1][k] + 2
      elif k:
        dp[i][j][k] = dp[i+1][j-1][k-1] + 2
      dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])
      
print(max(dp[0][ls-1]))


### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

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

r = []
g = []
b = []

for i in range(n):
    if s[i]=='R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)

# print(r,g,b)
ans = 0

for rr in r:
    for gg in g:
        for bb in b:
            if abs(gg-bb) != abs(rr-gg) and abs(rr-bb) != abs(gg-bb) and abs(rr-gg) != abs(rr-bb):
                ans += 1
print(ans)

### FIXED CODE ###

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

r = []
g = []
b = []

for i in range(n):
    if s[i]=='R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)

# print(r,g,b)
ans = 0

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

print(len(r)*len(g)*len(b) -ans)
### BUGGY CODE ###

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

if S[N-1] == '1':
    S += '0'
else:
    S += '1'

memo = []
now = S[0]
cnt = 1
for i in range(N):
    if S[i+1] == now:
        cnt += 1
    else:
        memo.append(cnt)
        cnt = 1
        now = S[i+1]

max = 0

if S[0] == '1':
    for i in range(len(memo)):
        if i%2 == 0:
            s = sum(memo[i:i+2*K+1])
        else:
            s = sum(memo[i:i+2*K])


        if s > max:
            max = s
else:
    for i in range(len(memo)):
        if i%2 == 1:
            s = sum(memo[i:i+2*K+1])
        else:
            s = sum(memo[i:i+2*K])


        if s > max:
            max = s

print(max)


### FIXED CODE ###

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

if S[N-1] == '1':
    S += '0'
else:
    S += '1'

memo = [1]
now = S[0]
cnt = 1
for i in range(N):
    if S[i+1] == now:
        cnt += 1
    else:
        cnt += 1
        memo.append(cnt)
        now = S[i+1]

n = len(memo)
for i in range(2*K+1):
    memo.append(N+1)

m = 0
l = []
if S[0] == '1':
    for i in range(n):
        if i%2 == 0:
            l.append(memo[i+2*K+1]-memo[i])
        else:
            l.append(memo[i+2*K]-memo[i])



        # if s > m:
        #     m = s
else:
    for i in range(n):
        if i%2 == 1:
            l.append(memo[i+2*K+1]-memo[i])
        else:
            l.append(memo[i+2*K]-memo[i])


        # if s > m:
        #     m = s

print(max(l))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a = list(map(lambda x: (str(bin(x))[2:]).zfill(65), a))
mod = 10**9 + 7
ans = 0
for i in range(65):
    cnt = 0
    for j in a:
        if j[-1*(i+1)] == "1": cnt += 1
    ans += cnt * (n-cnt) * pow(2, i, mod) % mod
    ans %= mod
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = list(map(lambda x: (str(bin(x))[2:]).zfill(65), a))
mod = 10**9 + 7
ans = 0
for i in range(65):
    cnt = 0
    for j in a:
        if j[-1*(i+1)] == "1": cnt += 1
    ans += cnt * (n-cnt) * pow(2, i, mod) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
L = [list(map(int,input().split())) for i in range(N)]
dp = [[0] * (W + 1) for i in range(N + 1)]

for i in range(N):
  weight = L[i][0]
  value = L[i][1]
  for w in range(W + 1):
    if w >= weight:
      dp[i + 1][w] = max(dp[i][w],dp[i][w - weight] + value)
    else:
      dp[i + 1][w] = dp[i][w]
      
print(dp[-1][W])

### FIXED CODE ###

N, W = map(int, input().split())
L = sorted( [ [int(i) for i in input().split()] for _ in range(N) ] )

dp = [0] * (W + 1)
cnt = 0

for w, v in L:
    #重さを足し合わせていき合計を求める
    cnt = cnt + w
    #W=重さの制約とこれまでの重さの合計のうち、
    #小さい方から品物iの重さまで、逆順にfor文を回す
    ##3,8-5,...15-7
    for i in range(min(cnt, W), w - 1, -1):
        #同じ重さでより価値が高い組み合わせがあれば価値を更新する
        ## w < Wの制約があり、i - wとその値を参照してから更新しているため、
        ## Wの制約を満たさない値を持つことはない
        ### 方法上、持ち得ない重さに持ち得ない値がつくことがあるが、
        ### それらが解 = 最大値になることはない
        ### (解を求める過程でついでに足されたり足されなかったりするだけなので)
        if dp[i] < dp[i - w] + v:
            dp[i] = dp[i - w] + v

print(max(dp))
### BUGGY CODE ###

N = int(input())

ans = []

for _ in range(N):
    S = input()
    if S not in ans:
        ans.append(S)

print(len(ans))

### FIXED CODE ###

N = int(input())

ans = {}
for _ in range(N):
    S = input()
    ans[S] = 1

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

A, B, K = map(int, input().split())
 
for i in range(A, B+1):
  if(A+K>i or B-K<i):
    print(i)

### FIXED CODE ###

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

#F
from operator import mul
from functools import reduce

r1, c1, r2, c2 = [int(i) for i in input().split()]
mod = 10**9 + 7

#pre-caluculation of the factorial
num = 10**7
fact=[0] * num
fact[0]=1
for i in range(1, num):
    fact[i] = (fact[i-1] * i) % mod

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    #return combinations_count(rr+cc+2, cc+1) - 1
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

ans = f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)
print(ans % mod)

### FIXED CODE ###

#F
from operator import mul
from functools import reduce

r1, c1, r2, c2 = [int(i) for i in input().split()]
mod = 10**9 + 7

#pre-caluculation of the factorial
num = 10**6*2+3
fact=[0] * num
fact[0]=1
for i in range(1, num):
    fact[i] = (fact[i-1] * i) % mod

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    #return combinations_count(rr+cc+2, cc+1) - 1
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

ans = f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)
print(ans % mod)
### BUGGY CODE ###

from itertools import accumulate

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

# pref = list(accumilate(a))

tab = [0] * n
for i in range(n):
	tab[i] = abs(sum(a[:i+1]) - sum(a[i+1:])) 
print(min(tab))

### FIXED CODE ###

from itertools import accumulate

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

pref = list(accumulate(a))

tab = [0] * n
for i in range(n):
	tab[i] = abs(pref[i] - (pref[-1] - pref[i])) 
print(min(tab))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split(" ")))

b = []

for i, a in enumerate(A):
    if i % 2 == 0:
        b = b + [a]
    else:
        b = [a] + b
        
if n % 2 == 1:
    b = b[::-1]
print(*b)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split(" ")))
      
if n % 2 == 0:
    print(*(A[1::2][::-1]+A[0::2]))
else:
    print(*(A[0::2][::-1]+A[1::2]))
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(map(str,input()))
lr = [0] * q
for i in range(q):
    lr[i] = list(map(int,input().split()))


for i in range(q):
    ans = 0
    st = lr[i][0]-1
    f = lr[i][1]-1
    for j in range(st,f):
        if s[j] == "A" and s[j+1] == "C":
            ans += 1  
    print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = [0] * (n+1)

for i in range(n):
    lr[i+1] = lr[i]+(1 if s[i:i+2] == "AC" else 0)

for i in range(q):
    st,fn = map(int,input().split())
    print(lr[fn-1] - lr[st-1])
### BUGGY CODE ###

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

ans=0
for i in a_uniq:
  count=a.count(i)
  if count>i:
    ans+=count-i
  elif count<i:
    ans+=count

print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dict={}
for i in a:
  if i not in dict:
    dict[i]=1
  else:
    dict[i]+=1

ans=0
for i in dict.keys():
  count=dict[i]
  if count>i:
    ans+=count-i
  elif count<i:
    ans+=count

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

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
            continue
        index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break

### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

S = input().split()
N = int(S[0])
M = int(S[1])
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_MAX = max(A)
B_MAX = max(B)
MAX = A_MAX if (A_MAX > B_MAX) else B_MAX

mod = int(1e9 + 7)

A_F_cnt = 0
B_F_cnt = 0

result = 1

for i in range(MAX, 0, -1):
    in_A = (i in A)
    in_B = (i in B)
    if (in_A and in_B):
        A_F_cnt += 1
        B_F_cnt += 1
    elif (in_A):
        result *= B_F_cnt
        A_F_cnt += 1 
    elif (in_B):
        result *= A_F_cnt
        B_F_cnt += 1
    else:
        coef = ((A_F_cnt * B_F_cnt) % mod ) - (N*M - i)
        if coef < 0:
            coef += mod
        result *= coef
    
print(int(result % mod))

### FIXED CODE ###

S = input().split()
N = int(S[0])
M = int(S[1])
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_MAX = max(A)
B_MAX = max(B)
MAX = A_MAX if (A_MAX > B_MAX) else B_MAX

mod = int(1e9 + 7)

A_F_cnt = 0
B_F_cnt = 0

sA = set(A)
sB = set(B)

result = 1

for i in range(MAX, 0, -1):
    in_A = (i in sA)
    in_B = (i in sB)
    if (in_A and in_B):
        A_F_cnt += 1
        B_F_cnt += 1
    elif (in_A):
        result *= B_F_cnt
        result %= mod
        A_F_cnt += 1 
    elif (in_B):
        result *= A_F_cnt
        result %= mod
        B_F_cnt += 1
    else:
        coef = ((A_F_cnt * B_F_cnt) % mod ) - (N*M - i)
        if coef < 0:
            coef += mod
        result *= coef
        result %= mod
    
    # print(in_A, in_B, A_F_cnt, B_F_cnt, result)

print(int(result % mod))
### BUGGY CODE ###

N = int(input())
L = [int(input()) for _ in range(N)]

for i in range(N):
    print(max(L[:i] + L[i + 1 :]))


### FIXED CODE ###

N = int(input())
L = [int(input()) for _ in range(N)]

Ls = sorted(L, reverse=True)
for i in range(N):
    if L[i] == Ls[0]:
        print(Ls[1])
    else:
        print(Ls[0])
### BUGGY CODE ###

import copy

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

a = list(set(K))
#print(a)
a_count = {}

for i in a :
    a_count[i] = K.count(i)

#print(a_count)



for i in range(N):
    a_count_2 = copy.deepcopy(a_count)
    
    a_count_2[K[i]] -= 1

    #print(a_count_2)
    ans = 0

    for i in a_count_2.values() :
        
        ans += i * (i-1)  // 2

    print(ans)

    pass

### FIXED CODE ###

import copy
from collections import Counter

N = int(input())
K = list(map(int,input().split()))
"""
N = 4
K = [1, 2 ,3 ,4]
"""
a = list(set(K))
#print(a)
a_count = {}



a_count = Counter(K)
#print(c)

#print(a_count)

ans_dict = 0
for l in a_count.values() :
        
    ans_dict += l * (l-1)  // 2

#print(ans_dict)

"""
for i in a_count :

    a_count_2 = copy.deepcopy(a_count)
    
    a_count_2[i] -= 1

    #print(a_count_2)
    
    ans_dict[i] = 0
    for l in a_count_2.values() :
        
        ans_dict[i] += l * (l-1)  // 2

#print(ans_dict)
"""

for i in K:
    print(ans_dict - (a_count[i]-1))
    pass
### BUGGY CODE ###

N,K=map(int,input().split())
X=list(map(int,input().split()))
X.sort()
ans=10**10

for i in range(N-K+1):
    L=X[i:i+K]
    if L[0]>0 and L[0]*L[-1]>0:
        ans=min(ans,L[-1])
    elif L[0]<0 and L[0]*L[-1]>0:
        ans=min(ans,-L[0])
    else:
        ans=L[-1]-L[0]+min(L[-1],-L[0])

print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
X=list(map(int,input().split()))
X.sort()
ans=10**10

for i in range(N-K+1):
    R=X[i+K-1]
    L=X[i]
    A=[ans, abs(L)+abs(R-L), abs(R)+abs(R-L)]
    ans=min(A)

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

import sys

_ = input()
S = input().strip()
idx = [i+1 for i in range(len(S)-1) if S[i:i+2] == 'AC']

for line in sys.stdin:
  l,r = list(map(int, line.strip().split(' ')))
  c = 0
  for i in idx:
    if l <= i <= r-1:
      c += 1
    else:
      continue
  print(c)


### FIXED CODE ###

import sys
_ = input()
S = input().strip()

ps = [0]*(len(S)+1)
for i in range(2, len(S)+1):
  ps[i] = ps[i-1]+int(S[i-2:i] == 'AC')

for line in sys.stdin:
  l,r = map(int, line.strip().split(' '))
  print(ps[r]-ps[l])
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(list(input()))
    s[i].sort()
    s[i] = ''.join(s[i])
    #print("{}".format(s[i]))

ans = 0
uniqs = set(s)
for orig in uniqs:
    occurence = s.count(orig)
    ans = ans + (occurence * (occurence -1)) // 2
print("{}".format(ans))

### FIXED CODE ###

n = int(input())
counter = {}
uniqs = set()
for i in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    counter[s] = counter.get(s,0) + 1
    uniqs.add(s)
    #print("{}".format(s[i]))

ans = 0
for orig in uniqs:
    occurence = counter.get(orig)
    ans = ans + (occurence * (occurence -1)) // 2
print("{}".format(ans))
### BUGGY CODE ###

import numpy as np 
#from numba import jit
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a,dtype="int64")

#@jit
def imo(a):
    imos=np.zeros(n+1,dtype="int64")
#print(arr[0])
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=np.zeros(n+1,dtype="int64")
    immo=np.cumsum(imos)
    return immo[:n]


for _ in range(min(k,41)):
    a=imo(a)
    
print(*a)


### FIXED CODE ###

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

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=[0]*(n+1)
    immo[0]=imos[0]
    for i in range(n):
        immo[i+1]=immo[i]+imos[i+1]

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)
### BUGGY CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

    dp = np.full(2**N, INF, np.int64)
    dp[0] = 0

    for i in range(M):

        next_dp = dp.copy()
        num, a = key[i]

        for j in range(2**N):
            if dp[j] == INF:
                continue
            else:
                next_num = j | num
                next_dp[j] = min(next_dp[j], dp[j])
                next_dp[next_num] = min(next_dp[next_num], dp[j] + a)

        dp = next_dp

    if dp[2**N - 1] == INF:
        ans = -1
    else:
        ans = dp[2**N - 1]

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

    dp = [INF for _ in range(2**N)]
    dp[0] = 0

    for i in range(M):
        num, a = key[i]
        for j in range(2**N):
            next_num = j | num
            dp[next_num] = min(dp[next_num], dp[j] + a)

    if dp[2**N - 1] == INF:
        ans = -1
    else:
        ans = dp[2**N - 1]

    print(ans)


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

import numpy as np
import heapq
N = int(input())
A = []
for _ in range(N):
  A.append(-1*int(input()))
A = np.array(A)
answer = []
for i in range(N):
  A_temp = np.delete(A, i).tolist()
  heapq.heapify(A_temp)
  answer.append(heapq.heappop(A_temp))
for i in range(N):
  print(-1*answer[i])

### FIXED CODE ###

import numpy as np
#import heapq
N = int(input())
A = []
for _ in range(N):
  A.append(int(input()))
A = np.array(A)
A_max_1 = np.max(A)
A_max_index = np.argmax(A)
A = np.delete(A, A_max_index)
A_max_2 = np.max(A)
answer = []
for i in range(N):
  if not i == A_max_index:
    answer.append(A_max_1)
  else:
    answer.append(A_max_2)
for i in range(N):
  print(answer[i])
### BUGGY CODE ###

class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


P = int(input())
c = Combi(P-1, P)
A = list(map(int,input().split()))
ans = [0 for i in range(P)]
for i in range(P):
    if A[i] != 0:
        ans[0] += 1
        for j in range(P):
            ans[j] -= c.C(P-1, j)*pow(-i, P-1-j,P) 
for i in range(P):
    ans[i] %= P
print(*ans)

### FIXED CODE ###

class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


P = int(input())
c = Combi(P-1, P)
A = list(map(int,input().split()))
ans = [0 for i in range(P)]
for i in range(P):
    if A[i] != 0:
        ans[0] += 1
        for j in range(P):
            ans[j] -= c.C(P-1, j)*pow(-i, P-1-j,P) 
for i in range(P):
    ans[i] %= P
print(*ans)
### BUGGY CODE ###

n,k = map(int,input().split())
sec = []
for i in range(k):
  l,r = map(int,input().split())
  sec.append([l,r])

dp = [0]*(n+1)
dp[0],dp[1] = 0,1
cumsum = [0]*(n+1)
cumsum[1] = 1
for i in range(2,n+1):
  for l,r in sec:
    if i>l:
      dp[i] += cumsum[i-l]-cumsum[max(0,i-r-1)]
  cumsum[i] = dp[i]+cumsum[i-1]
print(dp[n]%998244353)

### FIXED CODE ###

n,k = map(int,input().split())
sec = []
for i in range(k):
  l,r = map(int,input().split())
  sec.append([l,r])

mod = 998244353
dp = [0]*(n+1)
dp[0],dp[1] = 0,1
cumsum = [0]*(n+1)
cumsum[1] = 1
for i in range(2,n+1):
  for l,r in sec:
    if i>l:
      dp[i] += cumsum[i-l]-cumsum[max(0,i-r-1)]
  cumsum[i] = (dp[i]+cumsum[i-1])%mod
print(dp[n]%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=''
for i in range(n):
    ans+=str(a.index(i+1)+1)+' '
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(range(1,n+1))
dic=dict(zip(a,b))
dic=sorted(dic.items())
c=[]
for i in dic:
    c.append(i[1])
print(*c)
### BUGGY CODE ###

def merge(A, left, mid, right):
    global cnt
    inf = 1000000001
    n1, n2 = mid - left, right - mid
    L, R = [], []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])
    L.append(inf)
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        cnt += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


cnt = 0
input()
A = list(map(int, input().split()))
merge_sort(A, 0, len(A))
print(*A)
print(cnt)

### FIXED CODE ###

def merge(A, left, mid, right):
    global cnt
    inf = 1000000001
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        cnt += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


cnt = 0
input()
A = list(map(int, input().split()))
merge_sort(A, 0, len(A))
print(*A)
print(cnt)
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

current_arr = A
for k in range(K):
    next_arr = [0]*N
    for i, ai in enumerate(current_arr):
        for num in range(-ai, ai+1):
            ii = i + num
            if ii < 0 or N <= ii:
                continue
            next_arr[ii] += 1
    current_arr = next_arr
print(*next_arr)


### FIXED CODE ###

import sys
from itertools import accumulate

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

current_arr = A
if K > 41:
    print(*([N]*N))
else:
    for _ in range(K):
        imos = [0] * N
        ruiseki = [0] * (N+1)
        for i, ai in enumerate(current_arr):
            imos[max([0, i-ai])] += 1
            if i+ai+1 < N:
                imos[i+ai+1] -= 1
        for j, im in enumerate(imos):
            ruiseki[j+1] = ruiseki[j] + im
        current_arr = ruiseki[1:]
#print(imos)
#print(ruiseki)
#print(*accumulate(imos))
    print(*current_arr)