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

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

dp = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

ans = dp[one][two][three]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

print(dp[one][two][three])
### BUGGY CODE ###

import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for i in range(A)]
S = [-(10**11+1)] + S + [10**11+1]
T = [int(input()) for i in range(B)]
T = [-(10**11+1)] + T + [10**11+1]
X = [int(input()) for i in range(Q)]

for x in X:
    s_left = bisect.bisect_right(S, x)
    s_right = s_left - 1
    t_left = bisect.bisect_right(T, x)
    t_right = t_left - 1
    s1, s2 = S[s_left], S[s_right]
    t1, t2 = T[t_left], T[t_right]
    dis1 = abs(s1-x)+abs(s1-t1)
    dis2 = abs(s1-x)+abs(s1-t2)
    dis3 = abs(s2-x)+abs(s2-t1)
    dis4 = abs(s2-x)+abs(s2-t2)
    dis5 = abs(t1 - x) + abs(t1 - s1)
    dis6 = abs(t1 - x) + abs(t1 - s2)
    dis7 = abs(t2 - x) + abs(t2 - s1)
    dis8 = abs(t2 - x) + abs(t2 - s2)
    print(min(dis1, dis2, dis3, dis4, dis5, dis6, dis7, dis8))

### FIXED CODE ###

A, B, Q = map(int, input().split())
inf = 10 ** 11
S = [-inf] + [int(input()) for i in range(A)] + [inf]
T = [-inf] + [int(input()) for i in range(B)] + [inf]
X = [int(input()) for i in range(Q)]
import bisect

for q in range(Q):
    x = X[q]
    s1 = bisect.bisect_right(S, x)
    s2 = s1 - 1
    t1 = bisect.bisect_right(T, x)
    t2 = t1 - 1
    s1, s2 = S[s1], S[s2]
    t1, t2 = T[t1], T[t2]
    dis1 = abs(x - s1) + abs(s1 - t1)
    dis2 = abs(x - s2) + abs(s2 - t2)
    dis3 = abs(x - t1) + abs(t1 - s1)
    dis4 = abs(x - t2) + abs(t2 - s2)
    dis5 = abs(x - s1) + abs(s1 - t2)
    dis6 = abs(x - s2) + abs(s2 - t1)
    dis7 = abs(x - t1) + abs(t1 - s2)
    dis8 = abs(x - t2) + abs(t2 - s1)
    dis = min(dis1, dis2, dis3, dis4, dis5, dis6, dis7, dis8)
    print(dis)
### BUGGY CODE ###

l,r=map(int,input().split())
a=range(l,r+1)
m=float('inf')
for i in a:
    for j in range(i+1,r+1):
        m=min(m,(i*j)%2019)
print(m)


### FIXED CODE ###

l,r=map(int,input().split())
a=range(l,r+1)
m=float('inf')
for i in a:
    for j in range(i+1,r+1):
        m=min(m,(i*j)%2019)
        if m==0:
            print(0)
            exit()
print(m)
### BUGGY CODE ###

import collections
S=input()[::-1]
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[i])*d
    d*=10
    A[T%2019]+=1
ans=0
for cnt in A:
    ans+=cnt*(cnt-1)//2
print(ans)
















### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())

p=1
mod=10**9+7

for i in range(1,N+1):
    p = p*i

print(p%mod)

### FIXED CODE ###

N = int(input())

p=1
mod=10**9+7

for i in range(1,N+1):
    p = (p*i)%mod

print(p)
### BUGGY CODE ###

A, B = map(int, input().split())
ans = A
for i in range(A+1, B+1):
    ans = ans ^ i
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
def f(x):
    chk = x % 4
    if chk == 0:
        return x
    if chk == 1:
        return 1
    if chk == 2:
        return x + 1
    if chk == 3:
        return 0

if A != 0:
    A -= 1
print(f(A) ^ f(B))
### BUGGY CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    n=int(input())
    a=[int(input()) for i in range(n-1)]
    # print(a)
    dic=defaultdict(list)
    for i in range(n-1):
        p=a[i]
        dic[p].append(i+2)
    # print(dic)

    lst=[-1]*(n+1)

    def solve(m):
        if lst[m]!=-1:
            return lst[m]
        tmp=[]
        for i in dic[m]:
            tmp.append(solve(i))
        tmp.sort(reverse=True)
        rtn=0
        for i in range(len(tmp)):
            rtn=max(rtn,tmp[i]+i+1)
        lst[m]=rtn
        return rtn

    solve(1)
    # print(lst)
    print(max(lst))
main()

### FIXED CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    n=int(input())
    a=[int(input()) for i in range(n-1)]
    # print(a)
    dic={}
    for i in range(n-1):
        p=a[i]
        if p in dic:
            dic[p].append(i+2)
        else:
            dic[p]=[i+2]


    lst=[-1]*(n+1)

    def solve(m):
        if lst[m]!=-1:
            return lst[m]
        tmp=[]
        if m in dic:

            for i in dic[m]:
                tmp.append(solve(i))
        tmp.sort(reverse=True)
        rtn=0
        for i in range(len(tmp)):
            rtn=max(rtn,tmp[i]+i+1)
        lst[m]=rtn
        return rtn

    solve(1)
    # print(lst)
    print(max(lst))
main()
### BUGGY CODE ###

s = input()
q = int(input())

li = [input() for i in range(q)]

li2 = [0]*q
k= 0

for i in range(q):
    if len(li[i]) == 1:
        k += 1
        li2[i] = k
    else:
        li2[i] = k
        li3 = li[i].split()
        if (int(li3[1])+k) % 2 == 0:
            s = s + li3[2]
        else:
            s = li3[2] + s

if k % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

li = [input() for i in range(q)]
k = 0
ans = [s]
ans = deque(ans)

for i in li:
    if i == "1":
        k += 1
    else:
        if (int(i[2]) + k) % 2 == 0:
            ans.append(i[4])
        else:
            ans.appendleft(i[4])

ans = list(ans)
s = "".join(ans)
if k % 2 == 0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
count = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r + 1
    ans[index] = query(l, r+1)
for i in range(q):
    print(ans[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
count = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball: 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r + 1
    ans[index] = query(l, r+1)
for i in range(q):
    print(ans[i])
### BUGGY CODE ###

def lcm(x, y):
   if x > y:
       greater = x
   else:
       greater = y 
   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1
   return lcm

a,b = map(int,input().split())
print(lcm(a, b))

### FIXED CODE ###

a,b = map(int,input().split())
def gcd(a,b):
    if a < b:
        temp = b
        b = a 
        a = temp
    remainder = a % b
    if remainder == 0:
        return b
    else:
        return gcd(remainder,b)
 
def gys(a,b):
    remainder = gcd(a,b)
    print(int(a*b/remainder))
gys(a,b)
### BUGGY CODE ###

N = int(input())
T = [0]*N
A = [0]*N
for i in range(N):
    T[i],A[i] = map(int,input().split())

def aa(a,t,na,nt):
    c = 1
    while not(a<=na*c and t<=nt*c):
        c += 1
    return (na*c,nt*c)
t = T[0]
a = A[0]
for i in range(N):
    a,t = aa(a,t,A[i],T[i])
print(t+a)


### FIXED CODE ###

N = int(input())
T = [0]*N
A = [0]*N
for i in range(N):
    T[i],A[i] = map(int,input().split())

def aa(a,t,na,nt):
    c = max( (1+(a-1)//na,1+(t-1)//nt) )
    return (na*c,nt*c)
t = T[0]
a = A[0]
for i in range(N):
    a,t = aa(a,t,A[i],T[i])
print(t+a)
### BUGGY CODE ###

import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)

Q=int(input())
#累積和を求める
li = [0]*(H*W+2)
#print(H*W+2)
for i in range(1,D+1):
    #print('i=',i)
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        #print(j)
        h_n=int(np.where(f==j)[0])
        w_n=int(np.where(f==j)[1])
        li[j] = li[j-D]+abs(h_ - h_n)+abs(w_ - w_n)
        h_ = h_n
        w_ = w_n
        
        #print("diff",h_,w_)

        #print(j)
    
#print(li)
'''for i in range(1,26,4):
    print(i,li[i])
'''
# ここから計算
L = 17
R=25
#print(li[R]-li[L])
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])



### FIXED CODE ###

import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)
Q=int(input())
'''
li = [0]*(H*W+2)
for i in range(1,D+1):
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        h_n=int(np.where(f==j)[0])
        w_n=int(np.where(f==j)[1])
        li[j] = li[j-D]+abs(h_ - h_n)+abs(w_ - w_n)
        h_ = h_n
        w_ = w_n
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])
'''

li ={}
for i in range(H):
    for j in range(W):
        li[f[i][j]]=[i+1,j+1]
res=[0]*(H*W+1)
for i in range(1,D+1):
    for j in range(i+D,W*H+1,D):
        #print("j",j)
        #print(li[j][0],li[j][1])
        res[j] = res[j-D] +abs(li[j-D][0]-li[j][0]) + abs(li[j-D][1]-li[j][1])
#print(res)
for i in range(Q):
    L,R = na()
    print(res[R]-res[L])
### BUGGY CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)


### FIXED CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

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

x = int(input())

for a in range(9999):
    for b in range(9999):
        if a**5 - b**5 == x:
            print(a, b)
            exit()


### FIXED CODE ###

x = int(input())

l5 = [i**5 for i in range(0, 10000)]
for a5 in l5:
    for b5 in l5:
        if x == a5 - b5:
            print(int(a5**(1/5)), int(b5**(1/5)))
            exit()
        elif x == a5 + b5:
            print(int(a5**(1/5)), int((-1) * b5**(1/5)))
            exit()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	#print(inv2)

	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	#print(v)

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	#print(inv2)

	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	#print(v)

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)



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

n = int(input())
a_list = []

a_list = list(map(int,input().split()))
result = 1

for a in a_list:
    result *= a

if result > 10 ** 18:
    print(-1)
else:
    print(result)


### FIXED CODE ###

import sys

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

if 0 in a:
    print(0)
else:
    cur = 1
    for x in a:
        cur *= x
        if cur > 10 ** 18:
            print(-1)
            sys.exit()
    print(cur)
### BUGGY CODE ###

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

for k in range(K):
  B = [0] * N
  for i in range(N):
    s = i - A[i]
    if s < 0:
      s = 0
    l = i + A[i] + 1
    if l >= N:
      l = N
    for j in range(s, l):
      B[j] += 1
  A = B
  if min(A) == N:
    break
    
for b in B:
  print(b, end=" ")

### FIXED CODE ###

from numba import jit

@jit
def solve(N, K, A):
  for k in range(K):
    B = [0] * N
    for i in range(N):
      l = max(0, i - A[i])
      r = i + A[i] + 1
      B[l] += 1
      if r < N:
        B[r] -= 1

    for j in range(N - 1):
      B[j + 1] += B[j]
  
    if A == B:
      return B
    A = B
  return B
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = solve(N, K, A)
for b in B:
  print(b, end=" ")
### BUGGY CODE ###

#!/usr/bin/env python

import collections

def parse_input():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

if __name__ == "__main__":
    N, A = parse_input()
    counts = collections.defaultdict(int)
    for i in range(N):
        counts[A[i]] += 1

    for i in range(N):
        num = 0
        for a, c in counts.items():
            if a == A[i]:
                c -= 1
            num += max((c * (c - 1)) // 2, 0)
        print(num)


### FIXED CODE ###

#!/usr/bin/env python

import collections

def parse_input():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

if __name__ == "__main__":
    N, A = parse_input()
    counts = collections.defaultdict(int)
    for i in range(N):
        counts[A[i]] += 1

    total = 0
    subtracts = collections.defaultdict(int)
    for a, c in counts.items():
        num_patterns = max((c * (c - 1)) // 2, 0)
        subtracts[a] = num_patterns - max(((c - 1) * (c - 2)) // 2, 0)
        total += num_patterns

    for i in range(N):
        print(total - subtracts[A[i]])
### BUGGY CODE ###

n,q = (int(i) for i in input().split())
s = input()
x = [[i for i in input().split()] for i in range(q)]
l,r,s,f,R = 0,n+1,"#"+s+"#",1,0
while l+1<r:
    now = (l+r)//2
    for i,j in x:
        if s[now]==i:
            if j=="L": now-=1
            else: now+=1
        if now*(now-n-1)==0: break
    if now*(now-n-1) and f: f,R = 0,(l+r)//2
    if now: r = (l+r)//2
    else: l = (l+r)//2
L,r = l,n+1
if R: l = R
while l+1<r:
    now = (l+r)//2
    for i,j in x:
        if s[now]==i:
            if j=="L": now-=1
            else: now+=1
        if now*(now-n-1)==0: break
    if now-n-1: l = (l+r)//2
    else: r = (l+r)//2
print(r-L-1)

### FIXED CODE ###

n,q = (int(i) for i in input().split())
s = input()
x = [[i for i in input().split()] for i in range(q)]
l,r,s = 0,n+1,"#"+s+"#"
for i,j in x[::-1]:
    if l<=n and s[l+1]==i and  j=="L": l+=1
    elif s[l]==i and j=="R": l-=1
    if s[r-1]==i and j=="R": r-=1
    elif s[r]==i and j=="L": r+=1
print(max(0,r-l-1))
### BUGGY CODE ###



cache = {0: 1, 1: 1, 2: 2}
combo_cache = {}


def permutation(n):
    if n in cache:
        return cache[n]

    ret = n
    for i in range(n-1, 0, -1):
        if i in cache:
            ret *= cache[i]
            cache[n] = ret
            return ret

        ret *= i
    return ret


def combo(n, r):
    key = str(n) + "-" + str(r)
    if key in combo_cache:
        return combo_cache[key]

    x = permutation(n)
    y = permutation(n-r)
    z = permutation(r)
    combo_cache[key] = int(x // (y * z))
    return combo_cache[key]


count = int(input())
li = list(map(int, input().split()))
#
# data = open("input.txt", "r")
# l = data.read()
# li = list(map(int, l.split(" ")))


sli = sorted(li)

pair_a = 0
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

for j in range(0, len(sli) - 1):
    val = combo(i, sli[j])
    # print(str(sli[i]) + ", " + str(sli[j]) + ", " + str(val))
    if val > current_max:
        current_max = val
        pair_a = i
        pair_b = sli[j]

print(str(pair_a) + " " + str(pair_b))


### FIXED CODE ###

count = int(input())
li = list(map(int, input().split()))

sli = sorted(li)

pair_a = sli[len(sli) - 1]
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

diff = 10**9
for j in range(0, len(sli) - 1):
    h = pair_a / 2
    if abs(h - sli[j]) < diff:
        diff = abs(h - sli[j])
        pair_b = sli[j]

print(str(pair_a) + " " + str(pair_b))