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

from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        if first==1:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
        else:
            Q_sum+=A[i-1]
            len_Q+=1
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
           
right = P-1
left = N

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M

        
    if b<0:
        if A[P-1]<=target:
            right = i
        else:
            left = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(1,n-i):
        sum = a[i]+a[i+j]
        dif = j
        if sum==j:
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b = [0] * 10**6
ans=0
for i in range(n):
    if a[i]<(2*(10**5)):
        if i-a[i]>=0:
            ans+=b[i-a[i]]
        b[a[i]+i]+=1
print(ans)
### BUGGY CODE ###

import sys
h,w,m = map(int,input().split())
H = [0]*(h)
W = [0]*(w)
ls = []
for _ in range(m):
    a,b = map(int,input().split())
    ls.append([a-1,b-1])
    H[a-1] += 1
    W[b-1] += 1
hm = max(H)
wm = max(W)
a = [i for i in range(h) if H[i] == hm]
b = [j for j in range(w) if W[j] == wm]
for i in a:
    for j in b:
        if [i,j] not in ls:
            print(hm+wm)
            sys.exit()
print(hm+wm-1)

### FIXED CODE ###

h,w,m = map(int,input().split())
x = {}
y = {}
dic = {}
for _ in range(m):
    a,b = map(int,input().split())
    dic[(a,b)] = 1
    x[a] = x.get(a,0) + 1
    y[b] = y.get(b,0) + 1
p = max(x.values())
q = max(y.values())
cnt = 1
a = [i for i in x if x[i] == p]
b = [j for j in y if y[j] == q]
for i in a:
    for j in b:
        if dic.get((i,j),-1) == -1:
            cnt = 0
            break
    if not cnt:
        break
print(p+q-cnt)
### BUGGY CODE ###

S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3


print dp[-1][-1]%mod


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

L,R = (int(i) for i in input().split())

tmp = float("inf")

for i in range(L,R+1,1):
    for j in range(i+1,R+1):
        mod = i*j%2019
        if mod<tmp:
            tmp = mod
print(tmp)

### FIXED CODE ###

L,R = (int(i) for i in input().split())

tmp = float("inf")
count_i = 0
count_j = 0

for i in range(L,R+1):
    if count_i > 2019:break
    
    count_j = 0
    for j in range(i+1,R+1):
        if count_j >2019:break
        mod = i*j%2019
        if mod<tmp:
            tmp = mod
            
        count_j += 1
    count_i += 1
print(tmp)
### BUGGY CODE ###

ans = input()
q = int(input())
for i in range(q):
    #print(ans)
    Query = list(map(str,input().split()))
    #print(Query)
    if Query[0] == '2':
        if Query[1] == '1':
            ans = Query[2] + ans
        elif Query[1] == '2':
            ans += Query[2]
    else:
        ans = ans[::-1]
print(ans)


### FIXED CODE ###

from collections import deque
d = deque([])
ans = input()
d.append(ans)
q = int(input())
rev = True # Trueなら後ろに # Falseなら前に
for i in range(q):
    Query = list(map(str,input().split()))
    if Query[0] == '2':
        if Query[1] == '1':
            if rev:
                d.append(Query[2])
            else:
                d.appendleft(Query[2])
        elif Query[1] == '2':
            if rev:
                d.appendleft(Query[2])
            else:
                d.append(Query[2])
    else:
        rev = rev^True
output = ""
while d:
    output += d.pop()
if rev:
    print(output)
else:
    print(output[::-1])
### BUGGY CODE ###

#coding utf-8
_=input()
bars=[i for i in map(int,input().split())]
bars.sort(reverse=True)
stock=[]
ret=0
for bar in bars:
    count=bars.count(bar)
    if count>=4:
        if len(stock)!=0 and  bar not in stock:
            #print("ret bar bar")
            ret=bar*stock[0]
        else:
            #print("ret bar bar")
            ret=bar*bar
        break
    elif count>=2:
        if bar in stock:
            continue
        stock.append(bar)
        if len(stock)==2 :
            #print("ret stock stock")
            ret=stock[0]*stock[1]
            break
print(ret)

### FIXED CODE ###

#coding utf-8
import collections
_=input()
bars=[i for i in map(int,input().split())]
data=sorted(collections.Counter(bars).items(),key= lambda x: -x[0] )
stock=0
ret=0
for bar ,count in data:
    if count>=4:
        if stock:
            ret=stock*bar
            break
        else:
            ret=bar*bar
            break
    elif count>=2:
        if stock:
            ret=stock*bar
            break
        else:
            stock=bar
print(ret)
### BUGGY CODE ###

import itertools
import fractions
from functools import reduce

n = int(input())
a = [int(s) for s in input().split(' ')]

max = 1

for comb in itertools.combinations(a, n-1):
    ret = reduce(fractions.gcd, comb)
    if ret > max:
        max = ret

print(max)


### FIXED CODE ###

import itertools
import fractions
from functools import reduce

n = int(input())
a = [int(s) for s in input().split(' ')]

L = [0] * n
R = [0] * n

for i in range(len(a)):
    if i == 0:
        L[i] = a[i]
        R[n - 1] = a[n - 1]
    else:
        L[i] = fractions.gcd(L[i - 1], a[i])
        R[n - 1 - i] = fractions.gcd(R[n - i], a[n - 1 - i])

val = 1

for i in range(len(a)):
    ret = 0
    if i == 0:
        ret = R[i + 1]
    elif i == n - 1:
        ret = L[i - 1]
    else:
        ret = fractions.gcd(L[i - 1], R[i + 1])

    if ret > val:
       val = ret
        
print(val)
### BUGGY CODE ###

target = int(input())
curAns = 10 ** 12
 
for i in range(1,target):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

### FIXED CODE ###

n=int(input())
ans=n
for i in range(int(n**0.5),0,-1):
    if n%i==0:
        ans=n//i+i-2
        break
print(ans)
### BUGGY CODE ###

import collections
def main():
  N=int(input())
  str_list = [input() for _ in range(N)]
  c = collections.Counter(str_list)
  d=sorted(c.items(), key=lambda x:x[0], reverse=False)
  b = [x[1] for x in d]
  n = [x[0] for x in d]
  tgtind=[i for i, x in enumerate(b) if x == max(c.values())]
  for i in range(len(tgtind)):
    print(n[tgtind[i]])
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  n=int(input())
  arr=[input() for _ in range(n)]
  dic={}
  for i in range(n): #各単語の出現回数を数える
    if arr[i] not in dic:
      dic[arr[i]]=1
    else:
      dic[arr[i]]+=1
  largest=max(dic.values()) #最大の出現回数を求める
  ans=[]
  for keys in dic.keys():
    if dic[keys]==largest: #出現回数が最も多い単語を集計する
      ans.append(keys)
  ans=sorted(ans) #単語を辞書順に並べ替えて出力する
  for words in ans:
    print(words)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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

cl = [0 for i in range(n)]
ll = [x for x in set(l) if l.count(x) > 1]

if not ll:
    for i in range(n):
        print(0)
    sys.exit()

sum = 0
for i in ll:
    m = l.count(i)
    nc = combinations_count(m, 2)
    sum += nc
    # print(nc)
    cl[i - 1] = nc - int(nc * (m - 2) / m)

# print(sum)
# print(cl)
for i in l:
    print(sum - cl[i - 1])

### FIXED CODE ###

import collections

def combinations_count(n, r):
    return n * (n-1) // r


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

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    print(total-combinations_count(c[a], 2)+combinations_count(c[a]-1, 2))
### BUGGY CODE ###

import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,
a = [0]*n
for start in range(n):
    d = [-1] * n
    d[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        # v = que.get()
        v = pop()
        for nv in g[v]:
            if d[nv] < 0:
                d[nv] = d[v]+1
                # que.put(nv)
                add(nv)
    for i in d:
        a[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in a[1:]))


### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

K = int(input())
def gcd(i, j):
  if i%j==0:
    return j
  else:
    return gcd(j, i%j)
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=gcd(i, j)
    for k in range(1, K+1):
      _gcd=gcd(x, k)
      count += _gcd
print(count)

### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=math.gcd(i, j)
    for k in range(1, K+1):
      _gcd=math.gcd(x, k)
      count += _gcd
print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = [0]*n
for i in range(n):
    new = [e[1] for e in ls if e[0] == i+1]
    new.sort()
    di[i] = new
for j in range(m):
    a,b = ls[j][0],ls[j][1]
    p = di[a-1].index(b)
    q = 10**12 + (a)*10**6 +(p+1)
    print(str(q)[1:])



### FIXED CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])
### BUGGY CODE ###

from collections import deque

n, q = map(int, input().split())
to = [deque() for _ in range(n)]
score = [0 for _ in range(n)]
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):
    p, x = map(int, input().split())
    p -= 1
    score[p] += x

visited = [False for _ in range(n)]
def dfs(v):
    visited[v] = True
    stack = deque([v])
    while len(stack) > 0:
        u = stack[-1]
        if len(to[u]) > 0:
            w = to[u].popleft()
            if visited[w]:
                continue
            score[w] += score[u]
            visited[w] = True
            stack.append(w)
        else:
            stack.pop()

dfs(0)
print(*score)

### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
print(sum((n-r*z-g*y)/b==(n-r*z-g*y)//b and 0<=(n-r*z-g*y)/b<=3000 for z in range(3001) for y in range(3001)))

### FIXED CODE ###

r,g,b,n=map(int,input().split())
count=0
for x in range(n+1):
    for y in range(n-x+1):
        z=(n-r*x-g*y)//b
        if 0<=z<=3000:
            if r*x+g*y+z*b==n:count+=1
print(count)
### BUGGY CODE ###

def bubbleSort(A):
	cnt=0
	for i in range(len(A)):
		for j in range(len(A)-1,i,-1):
			if A[j]<A[j-1]:
				A[j],A[j-1]=A[j-1],A[j]
				cnt+=1
	return cnt

n=int(input())
A=list(map(int,input().split()))
print(bubbleSort(A))



### FIXED CODE ###

global cnt
cnt=0

def merge(A,left,mid,right):
    L=A[left:mid]
    R=A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    
    i=0
    j=0
    for k in range(left,right):
        global cnt
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1
            cnt+=mid-left-i

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(S,0,n)
print(cnt)
### BUGGY CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dst = [[INF]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] < dst[nh][nw]:
            dst[nh][nw] = dst[h][w]
            dq.appendleft((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
            dq.append((nh, nw))

print(-1 if dst[eh][ew]==INF else dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

import sys
x = input()
y = input().split()
r = sorted(y)
c = 0
while y != r:
    for i, j in enumerate(y[:-1]):
        if y[i] > y[i+1]:
            y[i], y[i+1] = y[i+1], y[i]
            c += 1
        else:
            break
print(" ".join(y))
print(c)

### FIXED CODE ###

x = int(input())
y = input()
y = list(map(int, y.split()))
r = sorted(y)
c = 0
while y != r:
    for i, j in enumerate(y[:-1]):
        if y[i] > y[i+1]:
            y[i], y[i+1] = y[i+1], y[i]
            c += 1
print(*y)
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
import os

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)

### FIXED CODE ###

import sys

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)
### BUGGY CODE ###

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

ans = 1
for i in a:
    ans *= i

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

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

ans = 1
for i in a:
    ans *= i
    if ans > 10 ** 18:
        print("-1")
        exit()

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

from itertools import product, chain

x, y, z, k = list(map(int, input().split(" ")))
a = sorted(list(map(int, input().split(" "))))
b = sorted(list(map(int, input().split(" "))))
c = sorted(list(map(int, input().split(" "))))

apb_sorted = sorted([a + b for a, b in product(a, b)])
ans_list = sorted(list(chain.from_iterable([[_c + ab for ab in apb_sorted] for _c in c])))
it = reversed(ans_list)
for _ in range(k):
    print(next(it))


### FIXED CODE ###

from itertools import product, chain

x, y, z, k = list(map(int, input().split(" ")))
a = sorted(list(map(int, input().split(" "))))
b = sorted(list(map(int, input().split(" "))))
c = sorted(list(map(int, input().split(" "))))

apb_sorted = sorted([a + b for a, b in product(a, b)])[-k:]
ans_list = sorted(
    list(chain.from_iterable([[_c + ab for ab in apb_sorted] for _c in c[:k]]))
)
it = reversed(ans_list)
for _ in range(k):
    print(next(it))
### BUGGY CODE ###

import copy
inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_list = []
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    prime_list.append(2)
for i in range(3, int(m // 2) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        prime_list.append(i)
import collections
k = collections.Counter(prime_list)
b = list(k.values())
import math
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

### FIXED CODE ###

import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1

dp = [[1 for _ in range(30)] for _ in range(n)]
for i in range(1, 30):
    for j in range(1,n):
        dp[j][i] = (dp[j - 1][i] + dp[j][i - 1]) % inf

for bb in b:
    ans *= dp[n - 1][bb]
    ans = ans % inf
print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    L = list(map(int, input().split()))
    res = 0
    for i, li in enumerate(L[:-2]):
        for j, lj in enumerate(L[i+1:-1]):
            for k, lk in enumerate(L[i+j+2:]):
                if li < lj + lk and lj < lk + li and lk < li + lj:
                    res += 1
    print(res)


### FIXED CODE ###

import bisect


if __name__ == '__main__':
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            ans += bisect.bisect_left(L, L[i]+L[j])-j-1
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  b.append(a[i])
  b = b[::-1]
  
b=[str(c) for c in b]
b=" ".join(b)
print(b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
m1 = n//2
if n%2==0:
  
  for i in range(m1):
    b.append(a[n-1-2*i])
  for i in range(m1):
    b.append(a[2*i])
else:
  
  for i in range(m1+1):
    b.append(a[n-1-2*i])
  for i in range(m1):
    b.append(a[1+2*i])
  
  
  
b=[str(c) for c in b]
b=" ".join(b)
print(b)
### BUGGY CODE ###

from collections import deque
n, q = map(int, input().split())
node = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  node[a-1].append([a-1, b-1])
  node[b-1].append([b-1, a-1])

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

already = [False]*n
not_yet = deque(node[0])
already[0] = True
for i in not_yet:
  already[i[1]] = True
while not_yet:
  key = not_yet.popleft()
  a, b = key[0], key[1]
  already[b] = True
  ans[b] += ans[a]
  for i in range(len(node[b])):
    p, q = node[b][i][0], node[b][i][1]
    if already[q]:
      continue
    not_yet.append(node[b][i])
    already[q] = True
  
print(*ans)

### FIXED CODE ###

from collections import deque

def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    ans = [0]*n
    for _ in range(q):
        p, x = map(int, input().split())
        ans[p-1] += x
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    
    while not_yet:
        key = not_yet.popleft()
        for value in tree[key]:
            if already[value]:
                continue
            already[value] = True
            not_yet.append(value)
            ans[value] += ans[key]
    
    print(*ans)

if __name__ == "__main__":
    main()