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

n,s=map(int,input().split())
MOD=998244353
import numpy as np
A=list(map(int,input().split()))
dp=[np.array([0]*(n+1)) for _ in range(s)]
dp=[np.array([1]+[0]*n)]+dp 
for i in range(n):
    u=A[i]
    for j in range(s,-1,-1):
        if j+u<=s:
            dp[j+u][1:]+=dp[j][:-1]
            dp[j+u]%=MOD
    #print(dp)

w=dp[s]
q=[2**(n-i) for i in range(n+1)]
ans=w*q%MOD
print(ans.sum()%MOD)
#print(w)

### FIXED CODE ###

mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
        dp[i+1][j] %= mod

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

n,k,q=map(int,input().split())
import sys
input = sys.stdin.readline
a=[int(input()) for _ in range(q)]
for _ in range(1,n+1):
   if k-q+a.count(_)>0:
      print("Yes")
   else:
      print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
import sys
input = sys.stdin.readline
a=[int(input()) for _ in range(q)]
import collections
c=collections.Counter(a)
for _ in range(1,n+1):
   if k-q+c[_]>0:
      print("Yes")
   else:
      print("No")
### BUGGY CODE ###

n=int(input())
ta=[]
t=0
a=0
ans=[[0,0]]
for i in range(n):
    p=[int(j) for j in input().split()]
    t=max(t,p[0])
    a=max(a,p[1])
    i,j=1,1
    while True:
        if p[0]*i>=t and p[1]*j>=a and p[0]*i>=ans[-1][0] and p[1]*j>=ans[-1][1]:
            ans.append([p[0]*i,p[1]*j])
            break
        i+=1
        j+=1

print(sum(ans[-1]))

### FIXED CODE ###

n=int(input())
ta=[]
t=0
a=0
ans=[[1,1]]
for i in range(n):
    p=[int(j) for j in input().split()]
    i=max(ans[-1][0]//p[0],ans[-1][1]//p[1])
    while True:
        if p[0]*i>=ans[-1][0] and p[1]*i>=ans[-1][1]:
            ans.append([p[0]*i,p[1]*i])
            break
        i+=1

print(sum(ans[-1]))
### BUGGY CODE ###

mod = 10 ** 9 + 7

s = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(s)):
    dp2 = [0] * 13
    for j in range(10):
        if (s[i] == '?') | (s[i] == str(j)):
            for k in range(13):
                dp2[(10 * k + j) % 13] += dp[k]
                dp2[(10 * k + j) % 13] %= mod
    dp = dp2
print(dp[5])

### FIXED CODE ###

mod = 10 ** 9 + 7

s = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(s)):
    dp2 = [0] * 13
    for j in range(10):
        if (s[i] == '?') | (s[i] == str(j)):
            for k in range(13):
                dp2[(10 * k + j) % 13] += dp[k]
                dp2[(10 * k + j) % 13] %= mod
    dp = dp2
print(dp[5])
### BUGGY CODE ###

n,m=map(int,input().split())
res=[0]*n

datas=[None]*m
for i in range(m):
  x,y,z=map(int,input().split())
  datas[i]=[min(x-1,y-1),max(x-1,y-1)]

datas=sorted(datas,key=lambda x:x[0])

maxi=0
for i in range(len(datas)):
  d=datas[i]
  if res[d[0]]==0 and res[d[1]]==0:
    maxi+=1
    res[d[0]]=maxi
    res[d[1]]=maxi
  elif res[d[0]]==0 and res[d[1]]!=0:
    res[d[0]]=res[d[1]]
  elif res[d[0]]!=0 and res[d[1]]==0:
    res[d[1]]=res[d[0]]
  elif res[d[0]]!=res[d[1]]:
    cor=min(res[d[0]],res[d[1]])
    dum=max(res[d[0]],res[d[1]])
    res[d[0]],res[d[1]]=cor,cor
    for i in range(len(res)):
      if res[i]==dum:
        res[i]=cor

count0=res.count(0)
ress=set(res)

print(count0 + len(ress) - (1 if 0 in ress else 0))


### FIXED CODE ###

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

parent=[i for i in range(n)]
rank=[0 for i in range(n)]

def find(a):
  if parent[a]==a:
    return a
  else:
    return find(parent[a])

def union(a,b):
  ar=find(a)
  br=find(b)
  if ar==br:
    return
  if rank[a]>rank[b]:
    parent[br]=ar
  else:
    parent[ar]=br
    if rank[a]==rank[b]:
      rank[a]+=1
      
def same(a,b):
  ar=find(a)
  br=find(b)
  return ar==br

q=[None]*m

for i in range(m):
  x,y,z=map(int,input().split())
  q[i]=[x-1,y-1]

for i in range(len(q)):
  union(q[i][0],q[i][1])
  
roots=[0]*len(parent)
for i in range(len(parent)):
  roots[i]=find(i)

print(len(set(roots)))
### BUGGY CODE ###

def replaceInt(N, M):
    N = abs(N-M)
    return N
    
N, M = [int(i) for i in input().split()]

if N == M :
    output = 0
elif N < M :
    if N <= M / 2:
        output = N
    else:
        output = abs(M-N)
else :
    if M == 1:
        output = 0
    else :
        output_candidates = [N]
        while True:
            N = replaceInt(N,M)
            if N in output_candidates or N > output_candidates[-1]:
                break
            output_candidates.append(N)
        output = min(output_candidates)
        
print(output)


### FIXED CODE ###

def replaceInt(N, M):
    N = abs(N-M)
    return N
    
N, M = [int(i) for i in input().split()]

if N == M :
    output = 0
elif N < M :
    if N <= M / 2:
        output = N
    else:
        output = abs(M-N)
else :
    if M == 1:
        output = 0
    else :
        N = N % M
        output_candidates = []
        while True:
            N = replaceInt(N,M)
            if N in output_candidates:
                break
            output_candidates.append(N)
        output = min(output_candidates)
        
print(output)
### BUGGY CODE ###

l, r = map(int, input().split())

LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]

ans = 2018

for i in range(l, r + 1):
  for j in range(i + 1, r + 1):
    ans = min(ans, LUT[i % 2019][j % 2019])
    if ans == 0:
      break
    
print(ans)

### FIXED CODE ###

def main():
  l, r = map(int, input().split())
  LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]
  ans = 2018
  m = 2019
  for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
      ans = min(ans, LUT[i % m][j % m])
      if ans == 0:
        return 0
  return ans

print(main())
### BUGGY CODE ###

from collections import Counter

def sol():
    N = int(input())
    A = list(map(int, input().split()))
    P = set(A)
    cnt = Counter(A)

    def divisors(n):
        divisors = []
        R = int(n**(0.5)) + 1
        for i in range(1, R):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        return divisors

    ans = 0
    for a in A:
        if cnt[a] > 1:
            continue
        for d in divisors(a):
            if d != a and d in P:
                break
        else:
            ans += 1

    print(ans)

sol()

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cntA = Counter(A)

A.sort()
V = set()

ans = 0
mx = max(A)
for a in A:
    if a in V:
        continue
    if cntA[a] == 1:
        ans += 1

    p = a
    while p <= mx:
        V.add(p)
        p += a

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

N,K=map(int,input().split())
if N%K==0:
    print(0)
    exit()
else:
    while True:
        if N <= abs(N-K):
            print(N)
            break
        else:
            N=abs(N-K)


### FIXED CODE ###

N,K=map(int,input().split())
print(min(N%K,-N%K))
### BUGGY CODE ###

import sys
_ = input()
S = input().strip()
for line in sys.stdin:
  l,r = list(map(int, line.strip().split(' ')))
  print(S[l-1:r].count('AC'))


### 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, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
if RD[S - 1] == -1:
  print(-1)
else:
  D = [[-1, -1, -1] for i in range(N)]
  Q = [[S - 1, 0]]
  while Q:
    q, d = Q.pop(0)
    if RD[q] == -1:
      continue
    m = (d + RD[q]) % 3
    if D[q][m] != -1:
      continue
    D[q][m] = d + RD[q]
    if m != 0:
      for adj in E[q]:
        Q.append([adj, d + 1])
  P = [d[0] for d in D if d[0] != -1]
  if P:
    print(min(P) // 3)
  else:
    print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
if M:
  Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % M
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % M
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)
### BUGGY CODE ###

number = list(map(int,input().split()))
line = list(map(int,input().split()))
 
num = number[0]
K = number[1]
dp = [0]* num

for i in range(1, num):
  I = min(i + 1 , K + 1)
  dp[i] = min([dp[i - k] + abs(line[i] - line[i - k]) for k in range(1 , I)])
  #kの範囲: k = 1,2,3...K 無理なときは k = 1,2..i
  
print(dp[-1])

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import deque

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))
 
stack = deque([0])
visited = []
ans = [0]*n
while stack:
    node = stack.popleft()
    visited.append(node)
    for child in graph[node]:
        if child[0] in visited:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2
 
[print(ans[i]) for i in range(n)]

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
ans = [-1]*n
ans[0] = 0
while stack:
    node = stack.pop()
    for child in graph[node]:
        if ans[child[0]]!=-1:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2

for a in ans:
    print(a)
### BUGGY CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
P = [int(p) for p in input().split()]

max_P = []
max = 0
for i in range(N-K+1):
    tmp = P[i:i+K]
    sum_dice = np.sum(tmp)
    if sum_dice > max:
        max = sum_dice
        max_P = tmp

ans = np.sum((np.array(max_P)+1)/2)

print(ans)

### FIXED CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
P = [int(p) for p in input().split()]

max = 0
sum = 0
for i in range(N):
    sum += P[i]
    if i >= K:
        sum -= P[i-K]
    if max < sum:
        max = sum
print((max+K)/2)
### BUGGY CODE ###

N, M = list(map(int,input().split()))
 
d = int(M/N)
 
if M%N == 0:
	print(d)
else: 
    ans = 1
    for i in range(M//N+1, 0, -1):
        if M % i == 0:
            if (M // i) >= N:
                print(i)
                break
	# i = 0
	# while True:
	# 	if M%(N+i+1) == 0:
	# 		print(int(M/(N+i+1)))
	# 		break
	# 	i += 1

### FIXED CODE ###

import math, sys, random

N, M = list(map(int,input().split()))
# N, M = 1111, 1000000000

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

d = int(math.floor(M/N))

if M%N == 0:
	print(d)
	sys.exit()

i = 0
f = False
while True:
	if M%(N+i+1) == 0:
		print(int(M/(N+i+1)))
		sys.exit()
	i += 1
	if i == 100000 and is_prime(M):
		print(1)
		sys.exit()
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())

N, M = tuple(li())

categories = [ tuple(li()) for _ in range(N) ]
categories.sort()

total = 0
def buy_M(cate, M, cost):
    if M <= 0:
        return cost
    if cate[0][1] >= M:
        cur_cost = cate[0][0] * M
        return cur_cost + cost
    else:
        rest = M - cate[0][1]
        cur_cost = cate[0][1] * cate[0][0]
        return buy_M(cate[1:], rest, cost + cur_cost)
print(buy_M(categories, M, 0))


### FIXED CODE ###

import sys
import bisect
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())

N, M = tuple(li())

categories = [ tuple(li()) for _ in range(N) ]
categories.sort()

total_cost = [(0, 0)]
for A, B in categories:
    total_cost.append((B + total_cost[-1][0], A * B + total_cost[-1][1]))
    idx = bisect.bisect_right( total_cost, (M, 0) )
total = total_cost[idx][1] + (M - total_cost[idx][0]) * categories[idx - 1][0]
print(total)
### BUGGY CODE ###

# -*- condig:utf-8 -*-

import collections
import sys
sys.setrecursionlimit(10000000)
n, q = map(int, input().split())

counter = [0 for _ in range(n+1)]
o = collections.defaultdict(int)
g = collections.defaultdict(list)

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

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x


def dfs(p, parent):
  counter[p] += o[p] + counter[parent]
  for i in g[p]:
    if i != parent:
      dfs(i, p)
 
dfs(1, 0)
print(*counter[1:])

 
  


### FIXED CODE ###


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

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

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

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
  p = todo.pop(-1)
  ct[p] += o[p]
  seen[p] = True
  for i in g[p]:
    if seen[i]:
      ct[p] += ct[i]
    else:
      todo.append(i)

print(*ct[1:])
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic=[]
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic.append(check)
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic[check]=1
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])
### BUGGY CODE ###

N=int(input())
rem=0
for i in range(1,N):
    rem+=i%(i+1)
print(rem)

### FIXED CODE ###

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

n = int(input())
a = list(map(int, input().split()))
score=1
for i in range(n):
    score = score* a[i]


if score <= 10 ** 18:
    print(score)
else:
    print(-1)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)

    if 0 in A:
        print('0')
        return
    prod=1
    for a in A:
        prod*=a
        if prod> 1000000000000000000:
            print('-1')
            return
    print(prod)

ans=main()
### BUGGY CODE ###

import sys
import numpy as np
from functools import lru_cache
from collections import deque

#input = sys.stdin.readline
#sys.setrecursionlimit(10 ** 5)

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = np.zeros([H + 1,W + 1],dtype = int)
dp[0][0] = 1
mod = (10 ** 9) + 7

def plus(a,b):
  a += b
  if a > mod:
    a %= mod
  return a

for i in range(H):
  for j in range(W):
    if i + 1 < H and grid[i + 1][j] == ".":
      dp[i + 1][j] = plus(dp[i + 1][j],dp[i][j])
      
    if j + 1 < W and grid[i][j + 1] == ".":
      dp[i][j + 1] = plus(dp[i][j + 1],dp[i][j])

print(dp[H - 1][W - 1])
#print(dp)

### FIXED CODE ###

import sys
import numpy as np
from functools import lru_cache
from collections import deque

#input = sys.stdin.readline
#sys.setrecursionlimit(10 ** 5)

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][0] = 1
mod = (10 ** 9) + 7

for i in range(H):
  for j in range(W):
    if i > 0 or j > 0:
      if grid[i][j] == "#":
        dp[i][j] = 0
      else:
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

print(dp[H - 1][W - 1])
#print(dp)
### BUGGY CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    x = input()
    for i in range(n):
        if x[i] == '1':
            tmp = x[:i] + '0' + x[i+1:]
        else:
            tmp = x[:i] + '1' + x[i+1:]
        tmp = int(tmp,2)
        cnt = 0
        while 1:
            if tmp == 0:
                print(cnt)
                break
            tmp = tmp%format(tmp, 'b').count('1')
            cnt += 1


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    x = input()
    k = int(x,2)
    c = x.count('1')
    kp = k%(c+1)
    if c > 1:
        kn = k%(c-1)
    
    for i in range(n):
        cnt = 1
        if x[i] == '1':
            if c == 1:
                print(0)
                continue
            mod = c-1
            tmp = (kn - pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        else:
            mod = c+1
            tmp = (kp + pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        print(cnt)


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

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,left,right):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


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

    if K >= 41:
        M = 41
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


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

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

#!/usr/bin/python

import sys

def main(argv):
    for line in sys.stdin:
        k, s = line.rstrip("\n").split(" ")
        k = int(k)
        s = int(s)
        counter = 0
        for x in xrange(0, k + 1):
            for y in xrange(0, k + 1):
                for z in xrange(0, k + 1):
                    if (x+y+z) == s:
                        counter += 1
        print counter

if __name__ == "__main__":
    main(sys.argv)

### FIXED CODE ###

#!/usr/bin/python

import sys

def main(argv):
    for line in sys.stdin:
        k, s = line.rstrip("\n").split(" ")
        k = int(k)
        s = int(s)
        counter = 0
        for x in xrange(0, k + 1):
            for y in xrange(x, k + 1):
                if x + y <= s:
                    z = s - x - y
                    if z >= y and z <= k:
                        if (x+y+z) == s:
                            if x == y and y == z:
                                counter += 1
                            elif x == y or y == z or x == z:
                                counter += 3
                            else: 
                                counter += 6
        print counter

if __name__ == "__main__":
    main(sys.argv)