CodeEff/ECCO huggingface dataset:
# Original solution
import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 50)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print((" ".join(map(str, A))))


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 100)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print((" ".join(map(str, A))))
# Original solution
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def func(A):
    aA = [0]*(2*N+10)
    for i, a in enu(A):
        st = max(0, 2*i-2*a-1)
        en = min(2*N, 2*i+2*a+1)
        aA[st] += 1
        aA[en] -= 1

    for i in range(2*N):
        aA[i+1] += aA[i]

    res = [val for i, val in enu(aA) if i%2==0]
    res = res[:N]
    return res

for _ in range(K):
    A = func(A)

print(*A)


# Optimized solution
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def func(A):
    # print('start')
    # print(A)
    all_N = True
    aA = [0]*(2*N+10)
    for i, a in enu(A):
        if a != N:
            all_N = False
        st = max(0, 2*i-2*a-1)
        en = min(2*N, 2*i+2*a+1)
        aA[st] += 1
        aA[en] -= 1

    # print(aA)
    for i in range(2*N):
        aA[i+1] += aA[i]

    # print(aA)

    res = [val for i, val in enu(aA) if i%2==0]
    res = res[:N]
    # print(res)
    return res, all_N

for _ in range(K):
    A, all_N = func(A)
    if all_N:
        break
    # print(*A)

print(*A)
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
for j in range(k):
  b = [0]*n
  for i in range(n):
    l = max(0, i-a[i])
    r = min(n, i+a[i]+1)
    b[l] += 1
    if r < n:
      b[r] -= 1
  for i in range(1, n): 
    b[i]+=b[i-1]
  a = b
  if a.count(n) == n:
    break
print((" ".join(list(map(str, a)))))
      
  


# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
for j in range(min(k, 41)):
  b = [0]*n
  for i in range(n):
    l = max(0, i-a[i])
    r = min(n, i+a[i]+1)
    b[l] += 1
    if r < n:
      b[r] -= 1
  for i in range(1, n): 
    b[i]+=b[i-1]
  a = b

print((" ".join(list(map(str, a)))))
# Original solution
#coding; utf-8
import copy
N, k = list(map(int,input().split()))
A = list(map(int,input().split()))
B = [0] * N
A = [0] + A
#B = copy.copy(A)
for j in range(k):
    #print(A)
    n_light = [0] * (N+1)
    for i in range(N):
        d = A[i+1]
        l = i+1-d
        r = i+1+d
        #print(l, r)
        n_light[max(l, 1)] += 1
        if r+1 <= N:# and l != r:
            n_light[r+1] -= 1
        #print(n_light)
    #print(n_light)
    for i in range(1,N):
        n_light[i+1] += n_light[i]
    n_str = [str(i) for i in n_light]
    A = n_light 
print((' '.join(n_str[1:])))
    


# Optimized solution
#coding; utf-8
import copy
N, k = list(map(int,input().split()))
A = list(map(int,input().split()))
B = [0] * N
A = [0] + A
#B = copy.copy(A)
#k = 10
for j in range(k):
    #print(A)
    n_light = [0] * (N+1)
    for i in range(N):
        d = A[i+1]
        l = i+1-d
        r = i+1+d
        #print(l, r)
        n_light[max(l, 1)] += 1
        if r+1 <= N:# and l != r:
            n_light[r+1] -= 1
        #print(n_light)
    #print(n_light)
    for i in range(1,N):
        n_light[i+1] += n_light[i]
    n_str = [str(i) for i in n_light]
    if len(set(n_light[1:])) == 1 and j > 2:
        #print(n_light)
        break
    #n_str = [str(i) for i in n_light]
    A = n_light
    #print(n_light) 
print((' '.join(n_str[1:])))
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * (n-1):
        break
print((" ".join(map(str, a))))


# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * n:

        break
print((" ".join(map(str, a))))
# Original solution
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    a = LI()

    for _ in range(K):
        x = [0] * N
        for i in range(N):
            s = i - a[i]
            if s < 0: s = 0
            x[s] += 1
            t = i + a[i] + 1
            if t < N:
                x[t] -= 1
        a = []
        cnt = 0
        for i in range(N):
            cnt += x[i]
            a.append(cnt)

    print(*a,sep=' ')


if __name__ == '__main__':
    main()


# Optimized solution
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    a = LI()

    for _ in range(K):
        x = [0] * N
        for i in range(N):
            s = i - a[i]
            if s < 0: s = 0
            x[s] += 1
            t = i + a[i] + 1
            if t < N:
                x[t] -= 1
        a = []
        cnt = 0
        finish = True
        for i in range(N):
            cnt += x[i]
            if cnt < N: finish = False
            a.append(cnt)
        if finish: break
    print(*a,sep=' ')


if __name__ == '__main__':
    main()
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
for _ in range(k):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print((' '.join(map(str,a))))


# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
for _ in range(min(k,int(n**0.5)+10)):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print((' '.join(map(str,a))))
# Original solution
def main():
    n,k,*a=list(map(int,open(0).read().split()))
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print((' '.join(map(str,a))))
main()

# Optimized solution
def main():
    n,k,*a=list(map(int,open(0).read().split()))
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print((' '.join(map(str,a))))
main()
# Original solution
def main():
    from itertools import accumulate
    n,k,*a=list(map(int,open(0).read().split()))
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            b[i-t if i>t else 0]+=1
            if i-~t<n:b[i-~t]-=1
        *a,=accumulate(b)
        if min(a)==n:break
    print((' '.join(map(str,a))))
main()

# Optimized solution
def main():
    from itertools import accumulate
    n,k,*a=list(map(int,open(0).read().split()))
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            if(j:=i-t)<0:j=0
            b[j]+=1
            if(j:=i-~t)<n:b[j]-=1
        *a,=accumulate(b)
        if min(a)==n:break
    print((' '.join(map(str,a))))
main()
# Original solution
import math
N,K=list(map(int,input().split()))
A=[0]*N
A=list(map(int,input().split()))

da=[0 for i in range(N)]
for k in range(K):
    B=[0 for i in range(N)]
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        B[l]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)


# Optimized solution
import math
N,K=list(map(int,input().split()))
A=[0]*N
A=list(map(int,input().split()))

da=[0 for i in range(N)]
for k in range(K):
    B=[0 for i in range(N)]
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        B[l]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    if(A==B):
        break
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)
# Original solution
def resolve():
        n, k = list(map(int, input().split()))
        a = list(map(int, input().split()))
        bn1 = [0] * n
        bn2 = [0] * n
        s = 0
        t = 0
        chec=0
        for _ in range(k):
            for i in range(n):
                b1 = max(i - a[i], 0)
                b2 = min(i + a[i], n - 1)
                bn1[b1] += 1
                bn2[b2] += 1
            for i in range(n):
                s += bn1[i]
                a[i] = s
            s = 0
            for i in range(1, n):
                t += bn2[i - 1]
                a[i] -= t
                if a[i]==n:
                    chec+=1

            if chec==n:
                break
            chec=0
            t = 0
            bn1 = [0] * n
            bn2 = [0] * n
        c = [str(x) for x in a]
        L = " ".join(c)
        print(L)
resolve()

# Optimized solution
def resolve():
        n, k = list(map(int, input().split()))
        a = list(map(int, input().split()))
        bn1 = [0] * n
        s = 0
        t = 0
        chec = 0
        for _ in range(k):
            for i in range(n):
                b1 = max(i - a[i], 0)
                b2 = min(i + a[i], n - 1)
                bn1[b1] += 1
                if b2<n-1:
                    bn1[b2+1] -= 1
            for i in range(n):
                s += bn1[i]
                a[i] = s
                if s==n:
                    chec+=1
            s = 0
            if chec == n:
                break
            chec = 0
            bn1 = [0] * n
        c = [str(x) for x in a]
        L = " ".join(c)
        print(L)
resolve()
# Original solution
n, k = list(map(int, input().split()))
As = list(map(int, input().split()))
 
 
def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs
 
 
for temp in range(min(k, 40)):
  As = change(As)
print((' '.join(map(str, As))))


# Optimized solution
import math
from itertools import accumulate
n, k = list(map(int, input().split()))
As = list(map(int, input().split()))
for i in range(min(41, k)):
  _As = [0]*(n+1)
  for j in range(n):
    l = max(0, j - As[j])
    r = min(n - 1, j + As[j])
    _As[l] += 1
    _As[r+1] -= 1
  As = list(accumulate(_As))[:-1]
print((' '.join([str(A) for A in As])))
# Original solution
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        tmp = A[i]
        B[max(i-tmp, 0)] += 1
        idx = min(i+tmp+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 2 * int(sqrt(N)):
        break

L = " ".join([str(x) for x in A])
print(L)


# Optimized solution
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial, log
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        B[max(i-A[i], 0)] += 1
        idx = min(i+A[i]+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 10 * int(log(N)):
        break

L = " ".join([str(x) for x in A])
print(L)
# Original solution
import math
from collections import Counter


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

for _ in range(k):
    l = []
    b = [0]*n
    for i in range(1, n+1):
        x = math.ceil(i-a[i-1]-0.5)
        y = math.floor(i+a[i-1]+0.5)
        l += list(range(x, y+1))
    c = Counter(l)
    for num in range(n):
        b[num] = c[num+1]
    a = b
print((' '.join(map(str, b))))

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

for _ in range(k):
    l = []
    b = [0]*n
    for i in range(1, n+1):
        x = i-a[i-1]-0.5
        y = i+a[i-1]+0.5
        l.append([x, y])
    for j in range(1, n+1):
        for x, y in l:
            if x <= j <= y:
                b[j-1] += 1
    a = b
print((' '.join(map(str, b))))
# Original solution
N, W = list(map(int, input().split()))
dp = [0]*(W+1)
max_weight = 0
for i in range(N):
    v, w, m = list(map(int, input().split()))
    n = 1
    while m > 0:
        m -= n
        _v, _w = v*n, w*n
        max_weight = min(W, max_weight + _w)
        for k in range(max_weight, _w-1, -1):
            if dp[k] < dp[k-_w] + _v:
                dp[k] = dp[k-_w] + _v
        n = m if n << 1 > m else n << 1

print((max(dp)))

# Optimized solution
N, W = list(map(int, input().split()))
dp = [0]*(W+1)
max_w = 0
for i in range(N):
    v, w, m = list(map(int, input().split()))
    n = 1
    while m > 0:
        m -= n
        _v, _w = v*n, w*n
        max_w = W if max_w+_w > W else max_w+_w
        for k in range(max_w, _w-1, -1):
            if dp[k] < dp[k-_w] + _v:
                dp[k] = dp[k-_w] + _v
        n = m if n << 1 > m else n << 1

print((max(dp)))
# Original solution
n, w = list(map(int, input().split()))

value = []
weight = []
num = []

for _ in range(n):
  vi, wi, ni = list(map(int, input().split()))
  value.append(vi)
  weight.append(wi)
  num.append(ni)

def to_digit(x):
  acc = 1
  ret = [0]
  while x >= acc:
    ret.append(acc)
    x -= acc
    acc *= 2
  if x:
    ret.append(x)
  return ret

num = list(map(to_digit, num))

dp = [0 for _ in range(w + 1)]
for i in range(n):
  vi = value[i]
  wi = weight[i]
  numsi = num[i]
  for k in numsi:
    for j in range(w, -1, -1):
      if j >= wi * k:
        dp[j] = max(dp[j], dp[j - wi * k] + vi * k)

print((dp[w]))


# Optimized solution
def main():
  n, w = list(map(int, input().split()))
  
  value = []
  weight = []
  num = []
  
  for _ in range(n):
    vi, wi, ni = list(map(int, input().split()))
    value.append(vi)
    weight.append(wi)
    num.append(ni)
  
  def to_digit(x):
    acc = 1
    ret = [0]
    while x >= acc:
      ret.append(acc)
      x -= acc
      acc *= 2
    if x:
      ret.append(x)
    return ret
  
  num = list(map(to_digit, num))
  
  dp = [0 for _ in range(w + 1)]
  for i in range(n):
    vi = value[i]
    wi = weight[i]
    numsi = num[i]
    for k in numsi:
      wik = wi * k
      vik = vi * k
      for j in range(w, wik - 1, -1):
        dp[j] = max(dp[j], dp[j - wik] + vik)
  
  print((dp[w]))

main()
# Original solution
n, knapsack = list(map(int, input().split()))
dp = [-1] * (knapsack + 1)
dp[0] = 0

for _ in range(n):
    value, weight, amount = list(map(int, input().split()))
    for i in range(knapsack - weight, -1, -1):
        if dp[i] < 0:
            continue
        for j in range(1, amount + 1):
            new_index = i + weight * j
            if new_index > knapsack:
                continue
            new_value = dp[i] + value * j
            if dp[new_index] < new_value:
                dp[new_index] = new_value

print((max(dp)))

# Optimized solution
n, knapsack = list(map(int, input().split()))
dp = [-1] * (knapsack + 1)
dp[0] = 0

for _ in range(n):
    value, weight, amount = list(map(int, input().split()))
    for i in range(knapsack - weight, -1, -1):
        if dp[i] < 0:
            continue
        for j in range(1, amount + 1):
            new_index = i + weight * j
            if new_index > knapsack:
                break
            new_value = dp[i] + value * j
            if dp[new_index] < new_value:
                dp[new_index] = new_value

print((max(dp)))
# Original solution
n, knapsack = list(map(int, input().split()))
dp = [-1] * (knapsack + 1)
dp[0] = 0

for _ in range(n):
    value, weight, amount = list(map(int, input().split()))
    for i in range(knapsack - weight, -1, -1):
        if dp[i] < 0:
            continue
        for j in range(1, amount + 1):
            new_index = i + weight * j
            if new_index > knapsack:
                break
            new_value = dp[i] + value * j
            if dp[new_index] < new_value:
                dp[new_index] = new_value

print((max(dp)))

# Optimized solution
n, knapsack = list(map(int, input().split()))
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [list(map(int, input().split())) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = min(amount, 1 << k)
        amount -= take
        gv, gw = value * take, weight * take
        for i in range(knapsack - gw, -1, -1):
            if dp[i] < 0:
                continue
            new_value = dp[i] + gv
            if dp[i + gw] < new_value:
                dp[i + gw] = new_value
        k += 1

print((max(dp)))
# Original solution
n, knapsack = list(map(int, input().split()))
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [list(map(int, input().split())) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take = amount
        amount -= take
        gv, gw = value * take, weight * take
        for i in range(knapsack - gw, -1, -1):
            dpi = dp[i]
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[i + gw] < new_value:
                dp[i + gw] = new_value
        k += 1

print((max(dp)))

# Optimized solution
n, knapsack = list(map(int, input().split()))
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [list(map(int, input().split())) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take = amount
        amount -= take
        gv, gw = value * take, weight * take
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw::-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print((max(dp)))
# Original solution
while 1:
  n=int(eval(input()))
  if not n:break
  f=1
  L={}
  for a,b,c in [list(map(int,input().split())) for i in range(n)]:
    a=str(a)
    d=b*c
    if a in L:
      if L[a]>=1e6:continue
      L[a]+=d
    else:L[a]=d
    if L[a] >= 1e6:
      print(a)
      f=0
  if f:print('NA')

# Optimized solution
while 1:
  n=int(eval(input()))
  if not n:break
  f=1
  L={}
  for a,b,c in [input().split() for i in range(n)]:
    d=int(b)*int(c)
    if a in L:
      if L[a]>=1e6:continue
      L[a]+=d
    else:L[a]=d
    if L[a]>=1e6:
      print(a)
      f=0
  if f:print('NA')
# Original solution
# coding: utf-8
# Here your code !
employeeSalesList = []

def resetDataset():
    del employeeSalesList[0 : len(employeeSalesList) + 1]

def readDataCount():
    return int(eval(input()))

def searchEmployeeSales(employeeId):
    for data in employeeSalesList:
        if data[0] == employeeId:
            return data
    
    newData = [employeeId, 0]
    employeeSalesList.append(newData)
    return newData

answerList = []
def printEmployeeOfDataset():
    found = False
    for data in employeeSalesList:
        if data[1] >= 1000000:
            answerList.append(data[0])
            found = True
    if not found:
        answerList.append("NA")

resetDataset()
dataCount = readDataCount()
while dataCount > 0:
    for _ in range(dataCount):
        employeeId, price, volume = list(map(int, input().split(" ")))
        employeeSales = searchEmployeeSales(employeeId)
        employeeSales[1] += price * volume
    printEmployeeOfDataset()
    resetDataset()
    dataCount = readDataCount()

for row in answerList:
    print(row)

# Optimized solution
# coding: utf-8
# Here your code !
employeeSalesList = []

def resetDataset():
    del employeeSalesList[0 : len(employeeSalesList) + 1]

def readDataCount():
    return int(eval(input()))

def searchEmployeeSales(employeeId):
    for data in employeeSalesList:
        if data[0] == employeeId:
            return data
    
    newData = [employeeId, 0]
    employeeSalesList.append(newData)
    return newData

def printEmployeeOfDataset():
    answerList = [data[0] for data in employeeSalesList if data[1] >= 1000000]
    if len(answerList) == 0:
        print("NA")
    else:
        print(("\n".join(map(str, answerList))))

resetDataset()
dataCount = readDataCount()
while dataCount > 0:
    for _ in range(dataCount):
        employeeId, price, volume = list(map(int, input().split(" ")))
        employeeSales = searchEmployeeSales(employeeId)
        employeeSales[1] += price * volume
    printEmployeeOfDataset()
    resetDataset()
    dataCount = readDataCount()
# Original solution
n = int(eval(input()))
li = [int(x) for x in input().split()]
X = sum(li)

ans = 100000000000
lix = []
for i in range(n-1):
    lix = li[:i+1]
    ans =min(ans ,abs(X - sum(lix)*2))
print(ans)

# Optimized solution
from itertools import accumulate
n = int(eval(input()))
li = [int(x) for x in input().split()]
X = list(accumulate(li))

ans = float("inf")
for i in range(n-1):
    ans =min(ans ,abs(X[-1] - X[i]*2))
print(ans)