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

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

ans=0
inf=10**9+7
for i in range(N-1):
    if A[i]!=0:
        for j in range(i+1,N):
            ans+=A[i]*A[j]
        ans=ans%inf    
print(ans)

### FIXED CODE ###

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

ans=0
inf=10**9+7
flag=True
total=0
for i in range(N):
    total+=A[i]
    total%=inf

for i in range(N): 
    total-=A[i]
    ans+=A[i]*total
    ans%=inf    
          
print(ans)
### BUGGY CODE ###

N,A,B=map(int, raw_input().split()) 
H=[ input() for i in range(N) ] 

def func(n , T):
	sa=A-B
	k=0
	for x in T:
		x-=n*B
		if x>0:
			if x%sa==0:
				k+=x/sa
			else:
				k+=(x/sa+1)
		
			if n<k:
				return False
	else:
			return True

l=max(H)/A
r=max(H)/B+1
while l!=r:
	m=(r+l)/2
	if func(m,H):
		r=m
	else:
		l=m+1
	#print l,r,m,func(m,H)

print l



### FIXED CODE ###

N,A,B= map(int,raw_input().split())
h=[input() for _ in range(N)]

high=max(h)
low=1

def enough(T):
	cnt=0
	for i in h:
		i-=T*B
		if i>0:
			if i%(A-B)==0:
				cnt+=i/(A-B)
			else:
				cnt+=i/(A-B)+1
	if cnt<=T:
		return True
	else:
		return False

ans=0
while low<=high:
	c= (low + high) / 2
	if enough(c):
		high=c-1
		ans=c
	else:
		low=c+1


print ans
### BUGGY CODE ###

import math
from functools import reduce
from itertools import combinations

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())
total = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            total += gcd(i,j,k)
print(total)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())
total = 0
for i in range(1,n+1):
    for j in range(i,n+1):
        for k in range(j,n+1):
            t = 1
            if i != k and i != j and j!= k:
                t = 6
            elif (i == j and i != k) or (i != j and j == k):
                t = 3
            total += gcd(i,j,k)*t
print(total)
### BUGGY CODE ###

from collections import defaultdict as dd
N,X,Y = map(int,input().split())

pdic = dd(lambda:0)

# count = 0

for i in range(1,N):
    for j in range(i+1,N+1):
        
#         count += 1
        
        # no shortcut
        d1 = j-i
        # with shortcut
        i2x = abs(X-i)
        y2j = abs(Y-j)
        d2 = i2x + y2j + 1
        
        dist = min(d1,d2)
        pdic[str(dist)] += 1
        
for n in range(1,N):
    print(pdic[str(n)])
    
# print("count:",count)

### FIXED CODE ###

from collections import defaultdict as dd
N,X,Y = map(int,input().split())

pdic = dd(lambda:0)

# count = 0

for i in range(1,N):
    for j in range(i+1,N+1):

#         count += 1

        # no shortcut
        d1 = j-i
        # with shortcut
        i2x = abs(X-i)
        y2j = abs(Y-j)
        d2 = i2x + y2j + 1

        dist = min(d1,d2)
        pdic[str(dist)] += 1

for n in range(1,N):
    print(pdic[str(n)])

# print("count:",count)
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
  l[i], r[i] = [int(j) for j in input().split()]
for i in range(q):
  print(s[l[i]-1:r[i]].count("AC"))
  

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
ans = ""
table = [0] * n
cnt = 0
for i in range(n-1):
  if s[i:i+2] == "AC":
    cnt += 1
  table[i+1] = cnt
for i in range(q):
  l, r = [int(j) for j in input().split()]
  print(table[r-1] - table[l-1])
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def zip(l):
    s = sorted(list(enumerate(l)), key = lambda x: x[1])
    ret = [0] * len(l)
    pre = -(10 ** 10)
    rank = 0
    for i, e in s:
        if e > pre:
            rank += 1
            pre = e
        ret[i] = rank
    return ret
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    z = zip(cum)
    nz = max(z)
    zb = Bit(nz)
    ret = 0
    for j in range(n+1):
        ret += zb.sum(z[j])
        zb.add(z[j], 1)
    return ret
l = min(a)
r = max(a) + 1
while(r - l > 1):
    mid = (r+l) // 2
    if 2 * med(mid) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(l)


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r + 1) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])
### BUGGY CODE ###

import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
lb = [0] * len(B)
for i in range(len(B)):
    lb[i]= bisect.bisect_left(A,B[i])

ans = 0    
for i in range(len(C)):
    temp = bisect.bisect_left(B,C[i])
    ans +=sum(lb[0:temp])


print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
lb = [0] * (len(B)+1)
lsum = [0] * (len(B)+1)
temp = 0
for i in range(len(B)):
    lb[i]= bisect.bisect_left(A,B[i])
    
for i in range(len(B)):
    lsum[i] = lb[i] +lsum[i-1]


ans = 0    
for i in range(len(C)):
    temp = bisect.bisect_left(B,C[i])
    ans +=lsum[temp-1]


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

K = int(input())
a = ""
ans = 0

if K%2 == 0:
    print(-1)

else:
    while True:
        a += "7"
        ans += 1
        if int(a)%K == 0:
            break
    print(ans)

### FIXED CODE ###

K = int(input())
a = ""
ans = 0
amari = 10

if K%2 == 0:
    print(-1)
elif K%5 == 0:
    print(-1)

else:
    if K%7 == 0:
        L = 9*K//7
    else:
        L = 9*K

    for p in range(10**6):
        if amari % L == 1:
            print(p+1)
            break
        else:
            amari = (amari*10)%L
### BUGGY CODE ###

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()

a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai:False for ai in a_ltk}

# 貪欲に足していく
for i in range(len(a_ltk)):
    cur = 0
    stack = []
    for j in range(i,len(a_ltk)):
        cur += a_ltk[j]
        stack.append(a_ltk[j])
        if cur >= k:
            for key in stack:
                need[key] = True
            stack.pop()
            cur -= a_ltk[j]

                
cnt = Counter(a_ltk)
ans = 0

for k,v in need.items():
    if not v:
        ans += cnt[k]
        
print(ans)

### FIXED CODE ###

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

# K以上のものはAから省く
B = []
for a in A:
    if a<K:
        B.append(a)

B.sort(reverse=True)

isNeeded = [False]*(len(B))
# iをスタックに入れる
for i in range(len(B)-1):
    res = B[i]
    stack = [i]
    for j in range(i+1,len(B)):
        res += B[j]
        stack.append(j)
        if res >= K:
            for s in stack:
                isNeeded[s] = True
            stack.pop()
            res -= B[j]
            
noNeed = len(B) - sum(isNeeded)
print(noNeed)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    c = [0] + [abs(h[1] - h[0])]
    for i in range(2, n):
        min_step = 10 ** 4
        for j in reversed(range(i)):
            if i - j > k:
                continue
            step = abs(h[i] - h[j]) + c[j]
            if step < min_step:
                min_step = step
        c.append(min_step)
    print(c.pop())


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] + [float("inf")] * (n-1)
    for i in range(1, n):
        for j in range(max(0, i-k), i):
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
    
    print(dp[-1])


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

x=int(input())
while(x%i<1 for i in range(2,x)):
  x+=1
print(x)


### FIXED CODE ###

x = int(input())
while any(x % i < 1 for i in range(2, x)): 
    x += 1
print(x)
### BUGGY CODE ###

N = int(input())
r = 1
for i in range(1, N+1):
    r *= i
print(r%((10**9)+7))


### FIXED CODE ###

import math
r = math.factorial(int(input()))
print(r%((10**9)+7))
### BUGGY CODE ###

import heapq


N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.remove(x)
      i += 1
    else:
      break
  if x_set:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    print(x_list[0])
  else:
    print(-1)

### FIXED CODE ###

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

s = input()
t = input()
num = set()

for i in range(len(s)):
    if s[i] != t[i]:
        if not i in num:
            a, b = s[i], t[i]
            s = s.replace(a, '-')
            s = s.replace(b, a)
            s = s.replace('-', b)
            num.add(a)
            num.add(b)
    num.add(s[i])
    num.add(t[i])
            
if s == t:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
s = list(input())
t = list(input())
a = [-1 for _ in range(26)]
b = [-1 for _ in range(26)]

for i in range(len(s)):
    num0, num1 = a[ord(s[i])-97], b[ord(t[i])-97]
    if num0 >= 0:
        if chr(num0+97) != t[i]:
            print('No')
            sys.exit()
    else:
        a[ord(s[i])-97] = ord(t[i])-97
        
    if num1 >= 0:
        if chr(num1+97) != s[i]:
            print('No')
            sys.exit()
    else:
        b[ord(t[i])-97] = ord(s[i])-97
            
print('Yes')
### BUGGY CODE ###

from collections import deque

a = input()
q = int(input())
rflag = 0
b = []
for i in range(q):
    b.append(input())
# print(b)
# print(len(b[0]))
ans = list(a)

for i in range(len(b)):
    if len(b[i]) == 1:
        rflag = (rflag ^ 1)
    else:
        c = int(b[i][2])
        # print("c="+b[i][2])

        if not rflag:

            if c == 1:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                tmp = deque(ans)
                tmp.appendleft(extend)
                ans = list(tmp)
            else:
                # print('ll')
                ans.append(b[i][4])
        else:
            if c == 1:
                ans.append(b[i][4])
            else:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                tmp = deque(ans)
                tmp.appendleft(extend)
                ans = list(tmp)
        # print(ans,rflag)

if not rflag:
    print("".join(ans))
else:
    print("".join(ans[::-1]))


### FIXED CODE ###

from collections import deque

a = input()
q = int(input())
rflag = 0
b = []
for i in range(q):
    b.append(input())
# print(b)
# print(len(b[0]))
ans = deque(list(a))

for i in range(len(b)):
    if len(b[i]) == 1:
        rflag = (rflag ^ 1)
    else:
        c = int(b[i][2])
        # print("c="+b[i][2])

        if not rflag:

            if c == 1:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                ans.appendleft(extend)
            else:
                # print('ll')
                ans.append(b[i][4])
        else:
            if c == 1:
                ans.append(b[i][4])
            else:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                ans.appendleft(extend)
        # print(ans,rflag)

if not rflag:
    print("".join(ans))
else:
    h="".join(ans)
    print(h[::-1])
### BUGGY CODE ###

n = int(input())
s = sorted([str(input()) for _ in range(n)])

S = set(s)
c_m = int(0)
l = []
ans = []
ans1 = []

for i in range(len(S)):
    a = S.pop()
    c_i = int(s.count(a))
    if c_i >= c_m:
        c_m = c_i
        l.append([c_m, a])
        continue

l.sort(reverse = True)
for i in range(len(l)):
    if l[0][0] == l[i][0]:
        ans.append(l[i][1])
        ans1 = sorted(ans)

for i in range(len(ans1)):
  print(ans1[i])


### FIXED CODE ###

n = int(input())
d = dict()
for _ in range(n):
    x = str(input())
    if x in d:
        d[x] += 1
        continue
    else:
        d[x] = 0

d_sort = sorted(d.items(), key=lambda d:d[1], reverse = True)
d_max = d_sort[0][1]

ans = []
for i in d_sort:
    if d_max == i[1]:
        ans.append(i[0])
    else:
        break

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

H, N = map(int, input().split())

attack_list = []
mp_list = []
for i in range(N):
    a, m = map(int, input().split())
    attack_list.append(a)
    mp_list.append(m)

inf = float('inf')
max_hp = H+max(attack_list)
dp = [inf for i in range(max_hp)]
dp[0] = 0

for i in range(H):
    for j in range(N):
        next_i = i + attack_list[j]
        dp[next_i] = min(dp[next_i], dp[i] + mp_list[j])

print(min(dp[H:max_hp+1]))


### FIXED CODE ###

H, N = map(int, input().split())

attack_list = []
mp_list = []
for i in range(N):
    a, m = map(int, input().split())
    attack_list.append(a)
    mp_list.append(m)

inf = float('inf')
max_hp = H+max(attack_list)
dp = [inf for i in range(max_hp)]
dp[0] = 0

for i in range(H):
    for j in range(N):
        next_i = i + attack_list[j]
        dp[next_i] = min(dp[next_i], dp[i] + mp_list[j])

print(min(dp[H:max_hp+1]))
### BUGGY CODE ###

import collections
import math


def combinations_count(n, r):
    return (n*(n-1)//2)
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
cnt = 0
ansx = []
ansy = []
ansy2 = []


for x, y in c.items():
    ansy.append(combinations_count(y, 2))
    ansy2.append(y-1)
    ansx.append(x)
sumall = sum(ansy)

for i in A:
    print(sumall - ansy2[ansx.index(i)])


### FIXED CODE ###

import collections
import math

N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
cnt = 0


sumall = 0
for x, y in c.items():
    sumall += (y*(y-1)//2)

for i in range(N):
    print(sumall - c[A[i]] + 1)
### BUGGY CODE ###

import heapq

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

for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        d = heapq.heappop(a)
        d = max(d , c)
        heapq.heappush(a, d)
        
print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
aa = [-1] * (2*n)
bc = []

for i in range(m):
    b,c = map(int,input().split())
    bc.append((c,b))
bc.sort(reverse = True)

i = 0
for j in range(m):
    if i >= n:
        break
    for k in range(bc[j][1]):
        aa[i] = bc[j][0]
        i += 1

j = 0
for i in range(n):
    if a[i] < aa[j]:
        a[i] = aa[j]
        j += 1
        
print(sum(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    s = input()
    a_indexes = [i for i, c in enumerate(s) if c == "A"]
    z_indexes = [i for i, c in enumerate(s) if c == "Z"]
    max_length = 0
    for a_index in a_indexes:
        for z_index in z_indexes:
            if z_index - a_index > max_length:
                max_length = z_index - a_index
    print(max_length + 1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    s = input()
    min_a_index = min([i for i, c in enumerate(s) if c == "A"])
    max_z_index = max([i for i, c in enumerate(s) if c == "Z"])
    print(max_z_index - min_a_index + 1)

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

a=input()
k=int(input())
x=5*pow(10,15)
i=0
while k>0:
    k-=pow(int(a[i]),x)
    i+=1
print(a[i-1])

### FIXED CODE ###

a=input()
k=int(input())
if int(a)<10:
    a=str(int(a)*11)
i=0
x=0
while k>=0:
    if a[i]=='1':
        k-=1
        i+=1
        if k==0:
            x=1
            k=-1
    else: 
        k=-1
print(a[i-x])
### BUGGY CODE ###

class DLList:
    class Cell:
        def __init__(self, data, pre, nex):
            self.data = data
            self.pre = pre
            self.nex = nex
    
    def __init__(self):
        self.top = DLList.Cell(None, None, None)

    def insert(self, x):
        if self.top.nex == None:
            w = DLList.Cell(x, self.top, self.top)
            self.top.nex = w
            self.top.pre = w
        else:
            w = DLList.Cell(x, self.top, self.top.nex)
            self.top.nex.pre = w
            self.top.nex = w
            
    def delete(self, x):
        w = self.top.nex
        while w != self.top:
            if w.data == x:
                w.pre.nex = w.nex
                w.nex.pre = w.pre
                break
            w = w.nex
            
    def deleteFirst(self):
        w = self.top.nex
        w.pre.nex = w.nex
        w.nex.pre = w.pre
     
    def deleteLast(self):
        w = self.top.pre
        w.pre.nex = w.nex
        w.nex.pre = w.pre 
           
    def pri(self):
        w = self.top.nex
        while w != self.top:
            if w.nex == self.top:
                print(w.data)
                break
            else:
                print(w.data,end=" ")
            w = w.nex

a = DLList()
n = int(input())
for i in range(n):
    s = input().split(" ")
    if s[0] == "insert":
        a.insert(int(s[1]))
    elif s[0] == "delete":
        a.delete(int(s[1]))
    elif s[0] == "deleteLast":
        a.deleteLast()
    elif s[0] == "deleteFirst":
        a.deleteFirst()
a.pri()

### FIXED CODE ###

from collections import deque
n = int(input())
a = deque()
for i in range(n):
    s = input().split(" ")
    if s[0] == "insert":
        a.appendleft(int(s[1]))
    elif s[0] == "delete":
        if int(s[1]) in a:
            a.remove(int(s[1]))
    elif s[0] == "deleteLast":
        a.pop()
    elif s[0] == "deleteFirst":
        a.popleft()
b = list(a)
for i in range(len(b)):
    if i == len(b)-1:
        print(b[i])
    else:
        print(b[i],end=" ")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
 
ans = set()
 
for i in range(n-2):
    for j in range(i+1, n-1):
        for l in range(j+1, n):
            ans.add(s[i] + s[j] + s[l])

print(len(ans))

### FIXED CODE ###

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

ans = 0
for i in range(1000):
    i = str(i)
    i = (3-len(i)) * '0' + i
    r = 0
    for j in range(n):
        if s[j] == i[r]:
            r += 1
        if r == 3:
            break
    if r == 3:
        ans +=1

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

n,k=map(int,input().split())
h=list(map(int,input().split()))
s=[float("INF")]*n
s[0]=0
for i in range(n):
    for j in range(k+1):
        if i+j<n:
            s[i+j]=min(s[i]+abs(h[i+j]-h[i]),s[i+j])
        else:
            break
print(s[-1])

### FIXED CODE ###

n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i,h in enumerate(a):
    if i!=0:
        g=0 if i-k<0 else i-k
        s[i]=min([abs(h-d)+p for d,p in zip(a[g:i],s[g:i])])
print(s[-1])
### BUGGY CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

    A, B, K = map(int, input().split())

    for val in range(A, B+1):
        if val<=A+K-1 or B-K+1<=val:
            print(val)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

    A, B, K = map(int, input().split())

    for val in range(A, B+1):
        if val<=A+K-1 or B-K+1<=val:
            print(val)

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

n, k = map(int, input().split())
a = list(map(int, input().split()))+[0]
s = [0 for _i in range(n+1)]
for i in range(n):
    s[max(0, i-a[i])] += 1
    s[min(n, i+a[i]+1)] -= 1   
a = s.copy()+[0]
for j in range(min(50, k-1)):
    t = [0 for _i in range(n+1)]
    for i in range(n):
        a[i] += a[i-1]
        t[max(0, i-a[i])] += 1
        t[min(n, i+a[i]+1)] -= 1
    a = t.copy()+[0]
for i in range(1, n):
    a[i] += a[i-1]
print(*a[:n])


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))+[0]
s = [0 for _i in range(n+1)]
for i in range(n):
    s[max(0, i-a[i])] += 1
    s[min(n, i+a[i]+1)] -= 1   
a = s.copy()+[0]
for j in range(min(100, k-1)):
    t = [0 for _i in range(n+1)]
    for i in range(n):
        a[i] += a[i-1]
        t[max(0, i-a[i])] += 1
        t[min(n, i+a[i]+1)] -= 1
    a = t.copy()+[0]
for i in range(1, n):
    a[i] += a[i-1]
print(*a[:n])
### BUGGY CODE ###

import numpy as np

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

    memo[(v, d)] = True
    if d == 0:
        res[v-1] = c
        return None

    dp(v, d-1, c)
    for e in dic.get(v, []):
        dp(e, d-1, c)


N, M = tuple(map(int, input().split(' ')))

dic = {}

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a] = dic.get(a, []) + [b]
    dic[b] = dic.get(b, []) + [a]

Q = int(input())

vdc = []

for q in range(Q):
    vdc.append(tuple(map(int, input().split(' '))))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


for i in range(N):
    print(int(res[i]))


### FIXED CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))