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

# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18
 
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
 
cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)
 
# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)
 
import heapq
 
len_max = 0
for i in range(10):
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue
 
# print("#", len_max)
 
if len_max % 3 == 1:
    print('Second')    
else:
    print('First')

### FIXED CODE ###

# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18
 
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
 
cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)
 
# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)
 
import heapq
 
len_max = 0
for i in range(2):
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue
 
# print("#", len_max)
 
if len_max % 3 == 1:
    print('Second')    
else:
    print('First')
### BUGGY CODE ###

def pred(i, lst):
  for cmpd in lst[:i+1]:
    if lst[i] > cmpd:
      return False
  return True

n = int(input())
p = [int(m) for m in input().split(' ')]

sum = 0
for i in range(n):
  if pred(i, p):
    sum += 1

print(sum)

### FIXED CODE ###

def pred(i, lst, offset):
  for cmpd in lst[offset:i+1]:
    if lst[i] > cmpd:
      return False
  return True

n = int(input())
p = [int(m) for m in input().split(' ')]

sum = 0
minimum = n + 1
for i in range(n):
  if p[i] < minimum:
    sum += 1
    minimum = p[i]

#sum = 0
#offset = 0
#for i in range(n):
#  if pred(i, p, offset):
#    sum += 1
#    offset = i

print(sum)
### BUGGY CODE ###

#!/usr/bin/env python3
from bisect import insort_left
from collections import deque
from math import ceil

n, k = map(int, input().split())
a = [[i, 1] for i in map(int, input().split())]
A = sorted(a)
while k > 0:
    q, c = A.pop()
    insort_left(A, [q * c / (c + 1), c + 1])
    k -= 1
print(ceil(A[-1][0]))


### FIXED CODE ###

#!/usr/bin/env python3
from bisect import bisect_left

n, k = map(int, input().split())
*a, = map(int, input().split())
def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
    return sum(-(-i // arg) - 1 for i in a) <= k


def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
print(meguru_bisect(0, max(a)))
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
w = []
for a in range(len(S)-1):
    if S[a] == 'A' and S[a+1] == 'C':
        w.append(1)
    else:
        w.append(0)
  
for n in range(Q):
    l, r = list(map(int, input().split()))
    v = w[(l-1):(r-1)]
    print(sum(v))


### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = input()
w = [0]
v = 0
for a in range(len(S)-1):
    if S[a] == 'A' and S[a+1] == 'C':
        v += 1
    w.append(v)
for n in range(Q):
    l, r = list(map(int, input().split()))
    print(w[r-1] - w[l-1])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
a_max = max(a)
for j in range(n):
  if a[j] != a_max:
    print(a_max)
  else:
    a.sort()
    a.reverse()
    print(a[1])

### FIXED CODE ###

n = int(input())
a = [0 for n in range(n)]
for i in range(n):
  a[i] = int(input())
a_max = max(a)
b = sorted(a)
a_second = b[n-2]
for j in range(n):
  if a[j] != a_max:
    print(a_max)
  else:
    print(a_second)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import collections

h,w = [int(i) for i in input().split()]
board = [input() for j in range(h)] # 縦「n」行

d4 = [[1,0],[0,1],[-1,0],[0,-1]]
memo = [[100000]*w for j in range(h)]


q = collections.deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            memo[i][j] = 0
            q.append((i,j,0))

while len(q) != 0:
#    print(memo)
    i,j,c = q.popleft()
#    print(i,j)
    for k in d4:
#        print(k)
        ii,jj = k
        if  i+ii < 0 or i+ii>=h or j+jj <0 or j+jj>=w:
#            print("out",i+ii,j+jj)
            continue
        if memo[i+ii][j+jj] > 10000:
#            print("put")
            q.append((i+ii,j+jj,c+1))
        memo[i][j] = min(c,memo[i][j])
    
    
ans = 0      
for i in range(h):
    for j in range(w):
        ans = max(ans,memo[i][j])

print(ans)





                
            
        

### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections

h,w = [int(i) for i in input().split()]
board = [input() for j in range(h)] # 縦「n」行

d4 = [[1,0],[0,1],[-1,0],[0,-1]]
memo = [[-1]*w for j in range(h)]
dist = [[100000]*w for j in range(h)]


q = collections.deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            memo[i][j] = 1
            q.append((i,j,0))

while len(q) != 0:
#    print(memo)
    i,j,c = q.popleft()
    dist[i][j] = c
    for k in d4:
#        print(k)
        ii,jj = k
        if  i+ii < 0 or i+ii>=h or j+jj <0 or j+jj>=w:
#            print("out",i+ii,j+jj)
            continue
        if memo[i+ii][j+jj] < 0:
#            print("put")
            q.append((i+ii,j+jj,c+1))
            memo[i+ii][j+jj] = 1

ans = 0      
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])

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

#!/usr/bin/env python3

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

    point = [1] * (N)
    point[0] = A[0]

    for i in range(1, N):
        point[i] = point[i - 1] * A[i]

    ans = point[K - 1]
    for i in range(N - K):
        tmp = point[K + i] / point[i]
        if ans < tmp:
            print('Yes')
        else:
            print('No')
        ans = tmp


if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

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

    ans = ['No'] * (N - K)
    for i in range(N - K):
        tmp = A[K + i] / A[i]
        if 1 < tmp:
            ans[i] = 'Yes'
    print("\n".join(ans))


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

n = int(input())

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

res = 1

for i in range(n):
    res *= a[i]

    if a[i] == 0:
        break


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


### FIXED CODE ###

n = int(input())

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

res = 1

if 0 in a:
    print(0)
else:
    for i in range(n):
        res *= a[i]

        if a[i] == 0:
            break
        if res > 10**18:
            print(-1)
            break


    if res > 10**18:
        pass
    else:
        print(res)
### BUGGY CODE ###

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

for i, j in enumerate(a):
    ai.append([i+1,j])
    ai[i].sort()

c = 0
for i in range(len(ai)):
    c += ai.count(ai[i])

print(c // 4)

### FIXED CODE ###

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

for i, j in enumerate(a):
    ai.append([i+1,j])
    ai[i].sort()

print(len(ai) - len(list(map(list,set(map(tuple, ai))))))
### BUGGY CODE ###

import numpy as np

#1. input
N = int(input())
A = np.array(list(map(int, input().split())))

ans = [np.sum(np.abs(np.concatenate([A[:i], A[i+1:], np.array([0])], axis=0) \
                                    - np.concatenate([np.array([0]), A[:i], A[i+1:]], axis=0))) for i in range(N)]

[print(ans[i]) for i in range(N)]

### FIXED CODE ###

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

#2. make distance list
a.append(0)
a.insert(0,0)
costs = []

for i in range(n+1):
    costs.append(abs(a[i+1]-a[i]))

#3. calculate each cost
total = sum(costs)
for i in range(n):
    print(total - costs[i] - costs[i+1] + abs(a[i+2]-a[i]))
### BUGGY CODE ###

b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1+=cmb(i-2,b-1,mod)
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2+=cmb(i-2,w-1,mod)
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)



### FIXED CODE ###

b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1%=mod
    t1+=cmb(i-2,b-1,mod)
    t1%=mod
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2%=mod
    t2+=cmb(i-2,w-1,mod)
    t2%=mod
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)
### BUGGY CODE ###

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)


for i in range(n):
  #print(sort[i], l)
  if l[i:] == [False]*len(sort[i:]):
    break
  if l[i] == False:
    continue
  
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False
      continue
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False


print(len([x for x in l if x]))
      


### FIXED CODE ###

from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
#print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(s-i+1):
        if s-i-j > k:
            continue
        elif j > k:
            break
        for l in range(s-i-j + 1):
            if i + j + l == s:
                n += 1
            elif i + j + l > s:
                break
print(n)


### FIXED CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(k+1):
        z = s - i - j
        if 0<= z <= k:
            n += 1
print(n)
### BUGGY CODE ###

from collections import defaultdict,deque
import copy 

N ,M ,K = [int(i) for i in input().split(' ')]
AB = defaultdict(deque)

arrive_size = [-1] * N

for _ in range(M):
    a, b = [int(i) for i in input().split(' ')]
    AB[a].append(b)
    AB[b].append(a)

CD = defaultdict(list)
for _ in range(K):
    c, d = [int(i) for i in input().split(' ')]
    CD[c].append(d)
    CD[d].append(c)

def DFS_size(s, Graph):
    stack = deque([s])
    size = 1
    arrive = [0] * N
    tree = set()
    while stack:
        v = stack[-1]
        arrive[v-1] = 1
        tree.add(v)
        if Graph[v]:
            w = Graph[v].popleft()
            if arrive[w-1] == 0:
                if not w in stack:
                    arrive[w-1] =1
                    stack.append(w)
        else:
            stack.pop()

    return tree

tree_all =[]
tree_size = [None] *N
for i in range(1,N+1):
    if arrive_size[i-1] == -1:
        Graph = copy.deepcopy(AB)
        tree = DFS_size(i,Graph)
        for t in tree:
            size = len(tree)
            for block in CD[t]:
                if block in tree:
                    size -= 1
            for friend in AB[t]:
                if friend in tree:
                    size -= 1
            tree_size[t-1] = size - 1

print(*tree_size)

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, M, K = map(int, input().split())

def dfs(v):
    size = 1
    for w in fr[v]:
        if ~roots[w]: continue
        roots[w] = roots[v]
        size += dfs(w)
    return size

fr = defaultdict(set)
for _ in range(M):
    a, b = [int(x) -1 for x in input().split()]
    fr[a].add(b)
    fr[b].add(a)
bl = defaultdict(set)
for _ in range(K):
    a, b = [int(x) - 1 for x in input().split()]
    bl[a].add(b)
    bl[b].add(a)

roots = [-1] * N
sizes = [-1] * N

for v in range(N):
    if ~roots[v]: continue
    roots[v] = v
    sizes[v] = dfs(v)

ans = []
for v in range(N):
    w = roots[v]
    res = sizes[w] - len(fr[v]) - sum(1 for u in bl[v] if roots[u] == w) -1
    ans.append(res)

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

import sys
from functools import lru_cache
# N = int(input())
X, Y = [int(i) for i in input().split()]

sys.setrecursionlimit(100000)


# @lru_cache(maxsize=None)
def solve(x, y):
    if x <= 0 or y <= 0:
        return 0
    if (x, y) == (1, 2) or (x, y) == (2, 1):
        return 1
    return (solve(x-1, y-2) + solve(x-2, y-1)) % (10**9+7)


print(solve(X, Y))



### FIXED CODE ###

import sys
# N = int(input())
X, Y = [int(i) for i in input().split()]
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

a_3 = 2 * Y - X
b_3 = 2 * X - Y
if a_3 % 3 != 0 or b_3 % 3 != 0 or a_3 < 0 or b_3 < 0:
    print(0)
    sys.exit(0)
a = a_3//3
b = b_3//3
print(cmb(a+b,a,mod))
### BUGGY CODE ###

R,C,K = map(int,input().split())

item = [[0]*C for _ in range(R)]
for i in range(K):
    r,c,v = map(int,input().split())
    item[r-1][c-1] = v
#print(item)

dp = [[[0]*4 for _ in range(C)] for _ in range(R)]

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            #print(i,j,k)
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j], max(dp[i-1][j]) + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j], max(dp[i-1][j]) + item[i][j])
                else:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                else:
                    dp[i][j][k] = max(0, 0 + item[i][j])

            #print(dp)
print(max(dp[R-1][C-1]))

### FIXED CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

R,C,K = map(int,input().split())

item = [[0]*C for _ in range(R)]
for i in range(K):
    r,c,v = map(int,input().split())
    item[r-1][c-1] = v
#print(item)

dp = [[0]*4 for _ in range(C)]
preview = [[0]*4 for _ in range(C)]

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            #print(i,j,k)
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j], max(preview[j]) + item[i][j])
                    else:
                        dp[j][k] = max(0, 0 + item[i][j], max(preview[j]) + item[i][j])
                else:
                    if j != 0:
                        dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j])
                    else:
                        dp[j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j])
                else:
                    dp[j][k] = max(0, 0 + item[i][j])

            #print(dp)
    preview = dp
print(max(dp[C-1]))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i + k < N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
        else:
            break
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i + k < N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N-1])
### BUGGY CODE ###

K,S = map(int,input().split())
ans=0
for x in range(K+1):
  for y in range(K+1):
    z= S-x-y
    if x+y+z ==S and 0<=z<=K:
      #print(x,y,z) 
      ans+=1
print(ans)

### FIXED CODE ###

K,S = map(int,input().split())
ans=0
for x in range(K+1):
  for y in range(K+1):
    z= S-x-y
    if x+y+z ==S and 0<=z<=K:
      #print(x,y,z) 
      ans+=1
print(ans)
### BUGGY CODE ###

import numpy as np

from collections import Counter
from itertools import combinations

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

cnter = Counter(S)
alpha = set(cnter)

ans = 0

for i in range(1, len(alpha) + 1):
    if i == 1:
       ans += len(S)
    else:
        for pat in combinations(alpha, i):
            ans += np.prod([value for key, value in cnter.items() if key in pat])

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

from collections import Counter

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

cnter = Counter(S)
alpha = set(cnter)

ans = 1

for i in alpha:
    ans *= (cnter[i] + 1)

print((ans - 1) % (10 ** 9 + 7))
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[];B=[]
retu=[[0]*N for _ in range(N)]
flg=[1]*N



for m in range(M):
  a,b =map(int,input().split())
  if H[a-1]<H[b-1]:
    flg[a-1]=0
  elif H[a-1]>H[b-1]:
    flg[b-1]=0
  else:
    flg[a-1]=flg[b-1]=0
  
print(flg.count(1))
 
  

### FIXED CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
flg=[1]*N


for m in range(M):
  a,b =map(int,input().split())
  if H[a-1]<H[b-1]:
    flg[a-1]=0
  elif H[a-1]>H[b-1]:
    flg[b-1]=0
  else:
    flg[a-1]=flg[b-1]=0
  
print(flg.count(1))
### BUGGY CODE ###

import math

k = int(input())

total = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            total += math.gcd(math.gcd(a,b),c)

print(total)


### FIXED CODE ###

import math

k = int(input())

total = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b,k+1):
            abc = {a,b,c}
            div = 1
            if len(abc) == 2:
                div = 3
            elif len(abc) == 1:
                div = 1
            elif len(abc) == 3:
                div = 6
            #print(str(a) + " " + str(b) + " " + str(c))
            add = div * math.gcd(math.gcd(a,b),c)
            #print(len(abc))
            #print(div)
            #print(add)
            total += add

print(total)
### BUGGY CODE ###

import math
from collections import defaultdict

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


def left_right(x, d):
    left = x - d - 0.5
    right = x + d + 0.5
    return left, right

printed = set()
printed_lst = []
bl = []
for x in range(K):
    dic = defaultdict(int)
    for i in range(N):
        l, r = left_right(i + 1, al[i])
        left = math.ceil(l)
        if left == 0:
            left += 1
        right = math.floor(r)
        for n in range(left, right + 1):
            dic[n] += 1
    al = list(dic.values())[:N]
    bl = [str(i) for i in al]
    bls = ''.join(bl)
    printed.add(bls)
    printed_lst.append(bls)
    if len(printed) != len(printed_lst):
        s = printed_lst.index(bls)
        s2 = x
        amari = (K-s)%(s2-s)
        ans = printed_lst[s+amari]
        print(ans)
        exit()

print(' '.join(bl))

### FIXED CODE ###

import math
from itertools import accumulate

N, K = map(int, input().split())
al = list(map(int, input().split()))
syusoku = [N] * N

for _ in range(K):
    s = [0] * N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right + 1 <= N - 1:
            s[right + 1] -= 1
        # print(left,right)
    al = list(accumulate(s))
    # print(al)
    if al == syusoku:
        print(*al)
        #print('end')
        exit()

print(*al)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))



ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)