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

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        j = 0
        while j < i or a[j] <= 0.5 * a[i]:
            if a[i] % a[j] == 0:
                break
            j += 1
        else:
            if not (n > 1 and i < n - 1 and a[i] == a[i + 1]):
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    max_a = max(a)

    dp = [True] * (max_a + 1)
    ans = 0

    for i in range(n):
        ai = a[i]
        if dp[ai]:
            if not (i < n - 1 and a[i] == a[i + 1]):
                ans += 1
            x = 1
            while ai * x < max_a + 1:
                dp[ai * x] = False
                x += 1

    print(ans)


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

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

for _ in range(INT()):
    a, b, c, d = MAP()
    if a < b or d < b:
        No()
        continue
    stock = a
    S = set()
    while 1:
        if stock >= b ** 2:
            stock = (a - c) % b + c
            if stock <= c:
                stock += d
        if stock < b:
            No()
            break
        if stock in S:
            Yes()
            break
        else:
            S.add(stock)
        stock -= b
        if stock <= c:
            stock += d


### FIXED CODE ###

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

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

for _ in range(INT()):
    a, b, c, d = MAP()

    # そもそも無理
    if a < b or d < b:
        No()
        continue
    
    # b個減ってd個増える繰り返しなので、このgより細かく値が動くことはない
    g = gcd(b, d)

    # cより大きくてb未満が存在するかどうか
    mn = bisearch_min(-INF, INF, lambda m: a%g + g*m > c)
    mx = bisearch_max(-INF, INF, lambda m: a%g + g*m < b)
    if mn > mx:
        Yes()
    else:
        No()
### BUGGY CODE ###

import numpy as np

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

arr0 = np.array(list(map(len, s.split('1'))))
arr0 = arr0[arr0!=0]

arr1 = np.array(list(map(len, s.split('0'))))
arr1 = arr1[arr1!=0]


ans = 0

if s[0] == '0':
    for i in range(len(arr0)):
        
        if i == 0:
            length = arr0[i:i+k].sum() + arr1[i:i+k].sum()
        else:
            length = arr0[i:i+k].sum() + arr1[i-1:i+k].sum()
        ans = max(ans, length)
        
else:        
    for i in range(len(arr0)):
        length = arr0[i:i+k].sum() + arr1[i:i+k+1].sum()
        ans = max(ans, length)
        

if len(s) == s.count('1'):
    print(len(s))
else:
    print(ans)

### FIXED CODE ###

import numpy as np

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

arr0 = np.array(list(map(len, s.split('1'))))
arr0 = arr0[arr0!=0]

arr1 = np.array(list(map(len, s.split('0'))))
arr1 = arr1[arr1!=0]


ans = 0

if s[0] == '0':
    for i in range(len(arr0)):
        
        if i == 0:
            length = arr0[i:i+k].sum() + arr1[i:i+k].sum()
        else:
            length = arr0[i:i+k].sum() + arr1[i-1:i+k].sum()
        ans = max(ans, length)
        
        if i+k > len(arr0):
            break
        
        
else:        
    for i in range(len(arr0)):
        
        
        length = arr0[i:i+k].sum() + arr1[i:i+k+1].sum()
        ans = max(ans, length)
        
        if i+k > len(arr0):
            break
        
        

if len(s) == s.count('1'):
    print(len(s))
else:
    print(ans)
### BUGGY CODE ###

N, C = map(int, input().split())
x = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    v.append(b)

clock = [0] * N
antiClock = [0] * N
for i in range(N):
    clock[i] = sum(v[:i+1]) - x[i]
    antiClock[i] = sum(v[i:]) - (C - x[i])

clock2antiClock = [(clock[i] - x[i] + max(antiClock[i+1:])) for i in range(N-1)]
antiClock2clock = [(antiClock[i] - (C - x[i]) + max(clock[:i])) for i in range(1, N)]

print(max([0] + clock + antiClock + clock2antiClock + antiClock2clock))

### FIXED CODE ###

N, C = map(int, input().split())
x = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    v.append(b)

R = [0] * N
L = [0] * N
for i in range(N):
    if i == 0:
        R[i] = v[i] - x[i]
        L[N-1-i] = v[N-1-i] - (C - x[N-1-i])
    else:
        R[i] = R[i - 1] + v[i] - (x[i] - x[i - 1])
        L[N-1-i] = L[N-i] + v[N-1-i] - (x[N-i] - x[N-1-i])

Rmax = [0] * N
Lmax = [0] * N
for i in range(N):
    if i == 0:
        Rmax[i] = R[i]
        Lmax[N-1-i] = L[N-1-i]
    else:
        Rmax[i] = max(Rmax[i-1], R[i])
        Lmax[N-1-i] = max(Lmax[N-i], L[N-1-i])

R2L = 0
L2R = 0
for i in range(N-1):
    R2L = max(R2L, R[i] - x[i] + Lmax[i+1])
    L2R = max(L2R, L[i+1] - (C - x[i+1]) + Rmax[i])

print(max(0, max(R), max(L), R2L, L2R))
### BUGGY CODE ###

S = input()
L = len(S)

while True:
    T = S[:]
    S = S.replace('10', '')
    S = S.replace('01', '')
    if S == T:
        break

print(L - len(S))


### FIXED CODE ###

S = input()

print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

import collections, sys
from heapq import *
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for stx in STX:
    s, t, x = stx
    heappush(event, [s - x, 1, x])
    heappush(event, [t - x, 0, x])
for d in D:
    heappush(event, [d, 2])
event.sort()
block = set()
for e in event:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            print(min(block))
        else:
            print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
    if e[1] == 0:
        block.remove(e[2])
        if m == e[2]:
            if block:
                m = min(block)
            else:
                m = float('inf')
    elif e[1] == 1:
        block.add(e[2])
        m = min(m, e[2])
    else:
        if block:
            if m == float('inf'):
                ans[e[2]] = -1
            else:
                ans[e[2]] = m
print(*ans, sep='\n')
### BUGGY CODE ###

n, m = list(map(int, input().split()))
card = list(map(int, input().split()))
data = []
for i in range(m):
    data.append(list(map(int, input().split())))
data.sort(key=lambda x:x[1])
count = 0
cnt = 0
for i in range(m):
    cnt = 0
    while min(card) < data[m - i - 1][1] and cnt < data[m - i - 1][0]:
        card[card.index(min(card))] = data[m - i - 1][1]
        count += 1
        cnt += 1
    if count >= n or min(card) > data[m - i - 1][1]:
        break
print(sum(card))

### FIXED CODE ###

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
count = 0
pre_index = 0
#print(data)
#print(a)
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    count = min(data[i][0], insert_index - pre_index)
    for j in range(pre_index, pre_index + count):
        if j >= n:
            break
        a[j] = 0
    ans += count * data[i][1]
    pre_index = pre_index + count
print(ans + sum(a))
### BUGGY CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
br = set(ar)
cr = []
for r in br:
    if ar.count(r) >= 4:
        cr.append(r)
        cr.append(r)
    elif ar.count(r) >= 2:
        cr.append(r)
cr = sorted(cr,reverse=True)
if len(cr) < 2:
    print(0)
else:
    print(cr[0] * cr[1])

### FIXED CODE ###

import collections
a = int(input())
ar = list(map(int,input().split(" ")))
br = collections.Counter(ar)
cr = []
for k,v in br.items():
    if v >= 4:
        cr.append(k)
        cr.append(k)
    elif v >= 2:
        cr.append(k)
cr = sorted(cr,reverse=True)
if len(cr) < 2:
    print(0)
else:
    print(cr[0] * cr[1])
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():
    L,R=map(int,input().split())
    minmod=10**10
    for i in range(L,R):
        for j in range(i+1,R+1):
            minmod=min(minmod,(i*j)%2019)
    print(minmod)

resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():
    L,R=map(int,input().split())
    if R-L<2018:
        print(min([(i*j)%2019 for i in range(L,R) \
                   for j in range(i+1, R+1)]))
    else:
        print(0)

resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
L = [int(v) for v in input().split()]

f = True
c = 0
while f:
    f = False
    
    for i in range(N):
        if f == False and L[i] % 2 == 0:
            c += 1
            L[i] = L[i] // 2
            f = True
            break
            
print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
L = [int(v) for v in input().split()]

c = 0
for v in L:
    if v % 2 == 0:
        while v % 2 == 0:
            v = v // 2
            c += 1
            
print(c)
### BUGGY CODE ###

N = input()
N = int(N)

def chose(i,j):
    count=0
    for x in range(1,N+1):
        if x//10**(len(str(x))-1)==i and x%10==j:
            count+=1
            
    return count

score = 0
for i in range(10):
    for j in range(10):
        score += chose(i,j)*chose(j,i)
        
print(score)
        

### FIXED CODE ###

N = input()
N = int(N)

c=[[0 for i in range(10)] for j in range(10)]

c[0][0]
for x in range(1,N+1):
    X=str(x)
    c[int(X[0])][int(X[-1])]+=1

score = 0
for i in range(10):
    for j in range(10):
        score += c[i][j]*c[j][i]
        
print(score)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    x,y=i,(n//i)*i
    ans+=((n//i)*(x+y)//2)
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    ans += (N//i)*(i+(i*(N//i)))//2
print(ans)
### BUGGY CODE ###

N,Q = map(int,input().rstrip().split())
S = input().rstrip()
for _ in range(Q):
    l, r = map(int,input().rstrip().split())
    ans = 0
    for i in range(l-1,r-1):
        if S[i]=='A' and S[i+1] == 'C':
            ans += 1
    print(ans)

### FIXED CODE ###

N,Q = map(int,input().rstrip().split())
S = input().rstrip()
a = [0]*N
for i in range(N):
    if i > 1:
        a[i] = a[i-1]
    if i != 0 and S[i-1]=='A' and S[i] == 'C':
        a[i] += 1
for _ in range(Q):
    l, r = map(int,input().rstrip().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      for k in range(j+1,l):
        if LS[i]+LS[j] > LS[k]:
          ans += 1
        else:
          break
print(ans)


### FIXED CODE ###

import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      k = bisect.bisect_left(LS,LS[i]+LS[j])
      ans += k-j-1
print(ans)
### BUGGY CODE ###

"""
i番目のゲートは LiからRiまでのIDカードのうちどれか1枚を持っていれば通過できます
"""

N, M = map(int, input().split())
arr = [0]*N

for i in range(M):
    L, R = map(int, input().split())
    for j in range(L,R+1,1):
        arr[j-1] += 1

print(arr.count(M))


### FIXED CODE ###

"""
i番目のゲートは LiからRiまでのIDカードのうちどれか1枚を持っていれば通過できます
"""

N, M = map(int, input().split())
left = 0
right =float("inf")

for i in range(M):
    L, R = map(int, input().split())
    if left<L:
        left = L
    if right > R:
        right = R

print(max(right-left+1,0))
### BUGGY CODE ###

line = input().split()
num = int(line[0]) + 1
sum = 0
for x in range(num):
    for y in range(num):
        for z in range(num):
            if x + y + z == int(line[1]):
                sum += 1
print(sum)                

### FIXED CODE ###

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

N=int(input())
for n in range(1,N+1):
    s=0
    for x in range(1,50):  
        for y in range(x,50):
            for z in range(y,50):
                fn=x*x+y*y+z*z+x*y+y*z+z*x
                if fn==n and x==y and x==z:
                    s=s+1
                if fn==n and x<y and y==z:
                    s=s+3
                if fn==n and x==y and y<z:
                    s=s+3              
                if fn==n and x<y and y<z:
                    s=s+6    
    print(s)  

### FIXED CODE ###

N=int(input())
ans=[0]*(N+1)
for x in range(1,101):  
    for y in range(1,101):
        for z in range(1,101):
            fn=x**2+y**2+z**2+x*y+y*z+z*x
            if fn>N:
                break
            else:
                ans[fn]=ans[fn]+1
for n in range(1,N+1):
    print(ans[n])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

def input():
    return sys.stdin.readline().rstrip('\n')

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

_C = {}

for i in range(M):
    a,b,c = list(map(int, input().split()))
    a -= 1
    b -= 1
    if c>L:
        continue
    _C[a*300+b] = c
    _C[b*300+a] = c

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
S = [0]*Q
T = [0]*Q

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]


# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(N):
        if D[i][j] <= L:
            _C[i*300+j] = 1
            _C[j*300+i] = 1

# ワーシャルフロイド法 again

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]
#STEP = [array('q', [0]*N) for i in range(N)]
STEP = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                STEP[i][j] = STEP[i][k] + STEP[k][j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# scipy version

import sys
from collections import deque
from array import array

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input():
    return sys.stdin.readline().rstrip('\n')

##### main

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

C = [[0]*N for _ in range(N)]

for i in range(M):
    a,b,c = list(map(int, input().split()))
    if c>L:
        continue
    C[a-1][b-1] = c

Q = int(input())

ST = [None]*Q

for i in range(Q):
    s, t = list(map(int, input().split()))
    ST[i] = (s-1,t-1)

dist_matrix, predecessors = floyd_warshall(csgraph=C, directed=False, return_predecessors=True)

# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(i+1,N):
        if dist_matrix[i][j] <= L:
            C[i][j] = 1

dist_matrix, predecessors = floyd_warshall(csgraph=C, directed=False, return_predecessors=True)

# answer
for q in range(Q):
    i,j = ST[q]
    step = dist_matrix[i][j]
    if step > 10**9:
        print(-1)
    else:
        print(int(step-1))
### BUGGY CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        L_slice = L[k:N]
        ite_right = bi(L_slice,right)
        count = count + (ite_right - 1)

print(count) 

### FIXED CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        ite_right = bi(L,right)
        count = count + (ite_right - k - 1)

print(count)
### BUGGY CODE ###

S=input()
K=len(str(S))
A=[[0 for v in range(K)] for j in range(2019)]
A[int(S[0])][0]+=1
for i in range(1,K):
 c=int(S[i])
 A[c][i]+=1
 for k in range(2019):
  d=(k*10+c)%2019
  A[d][i]+=A[k][i-1]
print(sum(A[0]))


### FIXED CODE ###

S=input()
T=len(S)
a=0
d=1
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(d))%2019
 b=a%2019
 mod[b]+=1
 d*=10
 d%=2019
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))
### BUGGY CODE ###

import sys
N, M = map(int, input().split())

lis_A = []
lis_B = []

for _ in range(N):
    A, B = map(int, input().split())
    lis_A.append(A)
    lis_B.append(B)

cost  = 0
count  = 0

while True:
    if N == 1:
        print(lis_A[0] * lis_B[0])
        sys.exit()
    saiyasu = lis_A.index(min(lis_A))



    #ものを買う時に、Mをオーバーするなら処理
    if (lis_B[saiyasu] + count) <= M:
        cost = ((lis_B[saiyasu] * lis_A[saiyasu]) + cost)
        count  = lis_B[saiyasu] + count
        lis_A.pop(saiyasu)
        lis_B.pop(saiyasu)
    else:
        cost = (((M - count) * lis_A[saiyasu]) + cost)
        break
print(cost)


### FIXED CODE ###

import sys
N, M = map(int, input().split())

lis_A = []
lis_B = []

for _ in range(N):
    A, B = map(int, input().split())
    lis_A.append(A)
    lis_B.append(B)

c = zip(lis_A, lis_B)
sorted_c = sorted(c)
lis_A, lis_B = zip(*sorted_c)


cost  = 0
count  = 0

while True:
    if N == 1:
        print(lis_A[0] * lis_B[0])
        sys.exit()


    for i in range(len(lis_A)):
        if (lis_B[i] + count) <= M:
            cost = (lis_A[i]*lis_B[i]) + cost
            count = lis_B[i] + count
        else:
            cost = (((M - count) * lis_A[i]) + cost)
            print(cost)
            sys.exit()
### BUGGY CODE ###

# import sys
from collections import deque
# sys.setrecursionlimit(10 ** 5)

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

def dfs():
    global counter
    done = [True for _ in range(N)]
    stack = deque([])
    done[0] = False
    for e in edge[0]:
        stack.append([e, 0])
    while stack:
        s = stack.pop()
        if done[s[0]]:
            done[s[0]] = False
            counter[s[0]] += counter[s[1]]
            for n in edge[s[0]]:
                stack.append([n, s[0]])
                
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p - 1] += x
dfs()

[print(c, end=" ") for c in counter]

### FIXED CODE ###

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N + 1)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

for _ in range(Q):
    p, x = map(int, input().split())
    counter[p - 1] += x

stack = [(0, -1)]
while stack:
    s, parent = stack.pop()
    counter[s] += counter[parent]
    for n in edge[s]:
        if n == parent:
            continue
        stack.append((n, s))

[print(c, end=" ") for c in counter[:N]]