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

import sys
input=sys.stdin.buffer.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

temp=[[0,0] for i in range(2**9)]

data=[[] for i in range(N+1)]
last=[-1 for i in range(N+1)]
for i in range(1,N+1):
    id=i
    while id>=2**9:
        data[i].append(vw[id])
        id//=2
    last[i]=id

def solve(v,L):
    n=len(data[v])
    for i in range(1,2**n):
        m=i.bit_length()
        temp[i][0]=temp[i-2**(m-1)][0]+data[v][m-1][0]
        temp[i][1]=temp[i-2**(m-1)][1]+data[v][m-1][1]
    ans=0
    for i in range(2**n):
        if L>=temp[i][1]:
            ans=max(ans,temp[i][0]+dp[last[v]][L-temp[i][1]])
    return ans

for i in range(int(input())):
    v,L=map(int,input().split())
    print(solve(v,L))


### FIXED CODE ###

import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())	
s=list(input())	

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    if s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        if s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
li = np.array(li)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))



### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())	
s=list(input())	

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    elif s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        elif s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
li = np.array(li)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))
### BUGGY CODE ###

n, k = list(map(int, input().split()))
move = []
for i in range(k):
    s, t = list(map(int, input().split()))
    m = list(range(s, t + 1))
    move += m

mod = 998244353

dp = [0] * (n)
dp[0] = 1

for i in range(n):
    p = i
    temp = 0
    for m in move:
        if m <= p:
            temp += dp[p - m]
    dp[p] += temp % mod

print(dp[n-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
move = []
for i in range(k):
    s, t = list(map(int, input().split()))
    move.append([s, t])

mod = 998244353

dp = [0] * (n + 1)
dp[1] = 1

ruiseki = [0] * (n + 1)
ruiseki[1] = 1

for i in range(n):
    p = i + 1
    temp = 0
    for j in range(k):
        s, t = move[j]
        r = max(0, p - s)
        l = max(0, p - t - 1)
        temp += ruiseki[r] - ruiseki[l]
    dp[p] += temp % mod
    ruiseki[p] = ruiseki[p - 1] + dp[p]

print(dp[n])
### BUGGY CODE ###

import sys,fractions
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9+7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
l = a[0]
for i in range(1,n):
    l = l*a[i]//fractions.gcd(l,a[i])
sm = 0
for i in range(n):
    sm = (sm + l//a[i])%R
print(sm)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9+7

def lcm_base(a,b):
    return (a*b)//gcd(a,b)

def inv(x):
    return pow(x,R-2,R)

n = inn()
a = inl()
#l = a[0]
#for i in range(1,n):
#    l = l*a[i]//gcd(l,a[i])
l = reduce(lcm_base,a,1)
sm = 0
for i in range(n):
    sm = (sm + inv(a[i]))%R
print((sm*l)%R)
### BUGGY CODE ###

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
 
red = sorted(list(map(int, input().split())), reverse=True)
gre = sorted(list(map(int, input().split())), reverse=True)
non = sorted(list(map(int, input().split())), reverse=True)
 
eat = []
 
for i in range(x):
    eat.append(red.pop(0))
 
for i in range(y):
    eat.append(gre.pop(0))
 
eat.sort()
 
for i in range(len(non)):
    n = non.pop(0)
    if eat[i] < n:
        eat[i] = n
    else:
        break
 
print(sum(eat))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())

red = sorted(list(map(int, input().split())), reverse=True)
gre = sorted(list(map(int, input().split())), reverse=True)
non = sorted(list(map(int, input().split())), reverse=True)

red = red[0:x]
gre = gre[0:y]

eat = red + gre + non

eat.sort(reverse=True)

print(sum(eat[0:x+y]))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.insert(0, 0)
a.append(0)

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

for j in range(n):
  answer = sum([abs(i) for i in gap[0:j]]) + abs(gap[j] + gap[j + 1]) + sum([abs(i) for i in gap[j + 2:]])
  print(answer)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.insert(0, 0)
a.append(0)

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

base = sum([abs(i) for i in gap])

for j in range(n):
  answer = base - (abs(gap[j]) + abs(gap[j + 1])) + abs(gap[j] + gap[j + 1])
  print(answer)
### BUGGY CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

S = []
E = []

for i in range(M):
  if ab[i][0] == 1:
    S.append(ab[i][1])
  if ab[i][1] == N:
    E.append(ab[i][0])

#print(S)
#print(E)

flag = False
for s in S:
  if s in E:
    flag = True
    break

if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')


### FIXED CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

S = []
E = []

for i in range(M):
  if ab[i][0] == 1:
    S.append(ab[i][1])
  if ab[i][1] == N:
    E.append(ab[i][0])

if set(S) & set(E):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

#!/usr/bin/env python
n, x, m = map(int, input().split())

tmp = x 
cnt = 0 
dup = 0 
a = [x] 
while True:
    tmp = (tmp*tmp)%m
    if tmp in a:
        dup = tmp 
        break
    cnt += 1
    a.append(tmp)

di = 0 
for i in range(len(a)):
    if a[i] == dup:
        di = i 

# block sum
b = []
bs = 0 
for i in range(di, len(a)):
    bs += a[i]
    b.append(a[i])

# block length
bl = len(a)-di
sumbl = 0 

ans = 0 
for i in range(di):
    ans += a[i]
ans += (n-di)//bl * bs
for i in range((n-di)%bl):
    ans += b[i]

print(ans)


### FIXED CODE ###

#!/usr/bin/env python
n, x, m = map(int, input().split())

tmp = x 
cnt = 0 
dup = 0 
a = [x] 
while True:
    tmp = (tmp*tmp)%m
    if tmp in a:
        dup = tmp 
        break
    cnt += 1
    a.append(tmp)

di = 0 
for i in range(len(a)):
    if a[i] == dup:
        di = i 

# block sum
b = []
bs = 0 
for i in range(di, len(a)):
    bs += a[i]
    b.append(a[i])

# block length
bl = len(a)-di
sumbl = 0 

ans = 0 
for i in range(di):
    ans += a[i]
ans += (n-di)//bl * bs
for i in range((n-di)%bl):
    ans += b[i]

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

from collections import deque
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[0 for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]] = 1
#print(rl)
for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j] == 0:
                d.append([[i,j],0])
rl=[[0 for i in range(n)] for i in range(n)]
al = []
key = 0
#print(l)
if len(d) == 0:
    key = 1
while len(d):
    now,day = d.pop()
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
    else:
        for i in l[now[0]][now[1]]:
            d.append([i,day])
    if day > n*(n-1)//2:
        key = 1
        break
if key == 1:
    print(-1)
else:
    print(max(al))

### FIXED CODE ###

from collections import deque
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[0 for i in range(n)] for i in range(n)]
dl = [[0 for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]] += 1
#print(rl)
for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j] == 0:
                d.append([[i,j],0])
al = []
key = 0
#print(l)
if len(d) == 0:
    key = 1
while len(d):
    #print(d)
    now,day = d.pop()
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
    else:
        for i in l[now[0]][now[1]]:
            if rl[i[0]][i[1]] == 1:
                rl[i[0]][i[1]] -= 1
                d.append([i,max(day,dl[i[0]][i[1]])])
            else:
                rl[i[0]][i[1]] -= 1
                dl[i[0]][i[1]] = max(day,dl[i[0]][i[1]])
    if day > n*(n-1)//2:
        key = 1
        break
md = 0
for i in range(n):
    md += sum(rl[i])
if key == 1 or md > 0:
    print(-1)
else:
    print(max(al))
### BUGGY CODE ###

n = int(input())
A = input().split(' ')

fl = "YES"
for i, a in enumerate(A):
  if a in A[i+1:]:
    fl = "NO"
    break

print(fl)

### FIXED CODE ###

n = int(input())
A = input().split(' ')

if len(A) == len(set(A)):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

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

if N==1:
    print(A[0]//(2**M))
    exit()

A.sort(reverse=True)

for i in range(M):
    A[0]=A[0]//2
    A.sort(reverse=True)


print(sum(A))


### FIXED CODE ###

import heapq

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

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

heapq.heapify(A)

for i in range(M):
    temp=heapq.heappop(A)
    heapq.heappush(A,(temp+1)//2)

print(-1*sum(A))
### BUGGY CODE ###

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

lst = []
for i in range(1,min(A, B)+1):
    if A % i == 0 and B % i == 0:
        lst.append(i)

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        if lst[i] % 2 == 0:
            pass
        else:
            for c in check:
                if lst[i] % c == 0:
                    break
            else:
                check.append(lst[i])
    print(len(check)+1)


### FIXED CODE ###

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

    return divisors

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

listA = make_divisors(A)
listB = make_divisors(B)
lst = list(set(listA) & set(listB))

lst.sort()

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)
### BUGGY CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
B = [0]*(N+1)
for i in range(N-1):
    B[A[i]] += 1
print('\n'.join([str(n) for n in B[1:]]))
### BUGGY CODE ###

mod =10**9+7
n,a,b = map(int,input().split())
ans = 2**n-1
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
ans -= cmb(n,a) + cmb(n,b)
print(ans%mod)

### FIXED CODE ###

mod =10**9+7
n,a,b = map(int,input().split())
ans = pow(2,n,mod)-1
def cmb(n,k):
    x,y = 1,1
    for i in range(k):
        x = x * (n-i) % mod
        y = y * (k-i) % mod
    return x * pow(y, mod-2, mod) % mod
ans -= cmb(n,a) + cmb(n,b)
print(ans%mod)
### BUGGY CODE ###

from bisect import *
N, Q = map(int, input().split())
c = 1
B = [1]
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, input().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    for i in range(lv, lw):
        w = (w - 2 + N) // N
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    print(v)


### FIXED CODE ###

from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, readline().split())
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, readline().split())
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")
### BUGGY CODE ###

n = int(input())

a = [int(x) for x in input().split()]

sum = a[0]

for i in range(1,len(a)):
    sum = sum * a[i]

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

### FIXED CODE ###

n = int(input())

a = [int(x) for x in input().split() ]
sum = a[0]

if 0 in a:
        sum = 0
else:
    for i in range(1,len(a)):
        sum = sum * a[i]
        if sum > 10**18:
            break
        


if sum > 10**18:
    print(-1)
else:
    print(sum)
### BUGGY CODE ###

N=int(input())
risuto=list(map(int,input().split()))
ans=1
for i in range(N):
    ans*=risuto[i]
if ans<=(10**18):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import math
N=int(input())
risuto=list(map(int,input().split()))
ans=1
kari=0
if 0 in risuto:
    print(0)
else:
    for j in range(N):
        kari+=math.log10(risuto[j])

    if kari<18:
        for i in range(N):
            ans*=risuto[i]
        print(ans) 
    elif kari==18:
        for i in range(N):
            ans*=risuto[i]
        if ans>10**18:
            print(-1)
        else:
            print(ans)
    else:
        print(-1)
### BUGGY CODE ###

import numpy as np
n, k, q = map(int, input().split())

A = np.zeros(n, dtype= int)
B = np.array([1]*n)

for i in range(q):
    t = int(input())
    A += B
    A[t-1] -= 1

for i in range(n):
    if A[i] < k:
        print('Yes')
    else :
        print('No')


### FIXED CODE ###

import numpy as np
n, k, q = map(int, input().split())

A = [k for _ in range(n)]

for i in range(q):
    t = int(input())
    A[t-1] +=1

for i in range(n):
    if A[i]-q > 0:
        print('Yes')
    else :
        print('No')
### BUGGY CODE ###

import heapq


n, m = map(int, input().split())
al = map(int, input().split())
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = map(int, input().split())
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

    if len(h) >= n:
        break


ans = sum( heapq.nlargest(n, h) )
print(ans)

### FIXED CODE ###

import heapq


n, m = map(int, input().split())
al = map(int, input().split())
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = map(int, input().split())
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

        if len(h) >= n:
            break


ans = sum( heapq.nlargest(n, h) )
print(ans)
### BUGGY CODE ###

"""
keyword: dfs
"""

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
to = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, p=-1): # v:これから見るnode、p:親node
    global ans
    for i in range(len(to[v])):
        u = to[v][i]
        if u == p: continue # 親nodeは確認済みなので見ない
        ans[u] += ans[v]
        dfs(u, v)

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

for i in range(q):
    v, x = map(int, input().split())
    v -= 1
    ans[v] += x

dfs(0)

print(*ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

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

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

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

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    from itertools import accumulate

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]

        if A==[n]*n:
            break
    
    

    print(*A[:-1])    
    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()