Harryxun/stf_run huggingface dataset:
import heapq as hp
# heapq.heappush(heap,item)
# heapq.heppop(heap) 最小値　最初のやつの取り出し
t=int(input())
for i in range(t):
    n=int(input())
# 左からkまでなら、+x lef[k]=[3,4,5]
    lef=[[] for i in range(n+1)]
    rig=[[] for i in range(n+1)]
    a=[]
    hp.heapify(a)
    ans=0
    lefcnt=0

    for i in range(n):
        k,l,r=map(int,input().split())
        if(l>=r):
            ans+=r
            lefcnt+=1
            tmp=l-r
            lef[k].append(tmp)
        else:
            ans+=l
            tmp=r-l
            rig[n-k].append(tmp)
    for i in range(lefcnt,0,-1):
        for j in lef[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp

    a=[]
    hp.heapify(a)
    for i in range(n-lencnt,0,-1):
        for j in rig[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp
    print(ans)

### FIXED CODE ###

import heapq as hp
# heapq.heappush(heap,item)
# heapq.heppop(heap) 最小値　最初のやつの取り出し
t=int(input())
for i in range(t):
    n=int(input())
# 左からkまでなら、+x lef[k]=[3,4,5]
    lef=[[] for i in range(n+1)]
    rig=[[] for i in range(n+1)]
    a=[]
    hp.heapify(a)
    ans=0
    lefcnt=0

    for i in range(n):
        k,l,r=map(int,input().split())
        if(l>=r):
            ans+=r
            lefcnt+=1
            tmp=l-r
            lef[k].append(tmp)
        else:
            ans+=l
            tmp=r-l
            rig[n-k].append(tmp)
    for i in range(n,lefcnt,-1):
        for j in lef[i]:
            hp.heappush(a,-j)           
    for i in range(lefcnt,0,-1):
        for j in lef[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp

    a=[]
    hp.heapify(a)
    for i in range(n,n-lefcnt,-1):
        for j in rig[i]:
            hp.heappush(a,-j)    
    for i in range(n-lefcnt,0,-1):
        for j in rig[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp
    print(ans)
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, log2
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

s = STR()
ans = 0
for i in range(len(s)):
    if s[i] == '+':
        ans += 1
    else:
        ans -= 1
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

s = STR()
ans = 0
for i in range(len(s)):
    if s[i] == '+':
        ans += 1
    else:
        ans -= 1
print(ans)
n,a,b = map(int,input().split())
ans = pow(2,n)-1
inf = 10**9 + 7
ans = ans% inf
aa = 1
bb = 1

for i in range(b):
    if i < a:
        aa = aa *(n-i) /(i+1)

    bb = bb *(n-i) /(i+1)

ans = int((ans -aa -bb) % inf)
print(ans)


### FIXED CODE ###

from functools import reduce

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

#combination高速化の裏技
def comb(N, A, MOD):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

#powはmodを引数にしてあまりを計算してくれる
print((pow(2, n, mod = mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)
K = int(raw_input())
S = len(raw_input())

M = 10**9 + 7

F = [1]
IF = [1]
for i in xrange(1, S + K + 1):
    F.append((F[-1] * i) % M)
    IF.append((IF[-1] * pow(i, M - 2, M)) % M)

def nCr(n, r):
    return (F[n] * IF[r] * IF[n-r]) % M

ans = 0
for i in xrange(K + 1):
    ans = (ans + nCr(i + S - 1, S - 1) * pow(25, i, M) * pow(26, K - i, M)) % M
print ans


### FIXED CODE ###

if input() in 'qwertyuiopasdfghjklzxcvbnm':
  print('a')
else:
  print('A')
a,b,k=list(map(int,input().split()))
 
ans=[]
 
for i in range(1,min(a,b)+1):
	if a%i==0 and b%i==0:
		ans.append(i)
print(ans[k+1])

### FIXED CODE ###

a,b,k=map(int,input().split())
 
ans=[]
 
for i in range(1,min(a,b)+1):
	if a%i==0 and b%i==0:
		ans.append(i)
print(ans[-k])
import math
def make_prime_list(num):
    if num < 2:
        return []
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break
        
        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0
    return [prime for prime in prime_list if prime != 0]

def prime_factorization(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1
        return dict_counter




if __name__ == '__main__':
    N, P = map(int, input().split())

    d = prime_factorization(P)

    cnt = 1

    for key, value in d.items():
        if value >= N:
            cnt *= key

    print(cnt)


### FIXED CODE ###

import math
def make_prime_list(num):
    if num < 2:
        return []
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break
        
        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0
    return [prime for prime in prime_list if prime != 0]

def prime_factorization(num):
    if num <= 1:
        return {1 : 1}
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1
        return dict_counter




if __name__ == '__main__':
    N, P = map(int, input().split())

    d = prime_factorization(P)

    cnt = 1

    for key, value in d.items():
        while value >= N :
            cnt *= key
            value -= N
    if N == 1:
        print(P)
    else:
        print(cnt)
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))


### FIXED CODE ###

a, b, c = map(int, (input().split()))
print(max(c - (a - b), 0))
O = input()
E = input()

ans = ''
for i in range(min(len(O), len(E)):
    ans += O[i]
    ans += E[i]

if len(O) > len(E):
    ans += O[i]
elif len(O) < len(E):
    ans += E[i]

print(ans)

### FIXED CODE ###

print("".join([a+b for a,b in zip(input(),input()+" ")]))
s = list(str(input()))
b = {}
b[0] = 1
c_ = 0
s = s.reverse()
for i in s:
  c = (c_+int(i)*10**num)%2019
  if c in b:
    b[c] += 1
  else:
    b[c] = 1
  c_ = c
ans = 0
for i in b.values():
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
MOD = 2019
a =[0]*MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
  c = (c_+int(i)*t)%MOD
  a[c] += 1
  t *= 10
  t %= MOD
  c_ = c
for i in a:
  ans += i*(i-1)//2
print(ans)
N = int(input())
h = list(map(int,input().split()))
flag = 0
if N == 1:
    print("Yes")
else:
    for i in range(N-1):
        if h[i] > h[i+1]:
            h[i] -= 1
    for i in range(N-1):
        if h[i] <= h[i+1]:
            flag = 1:
        else:
            flag = 0:
            break
    if flag == 1:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
ans = True
for i in range(N-2,-1,-1):
    if h[i] > h[i+1]:
        h[i]-=1
for i in range(N-1):
    if h[i] <= h[i+1]:
        ans = True
    else:
        ans = False
        break
if ans:
    print('Yes')
else:
    print('No')
N,x = map(int, input().split())
A = sorted(map(int, input().split()))

S = 0
c = 0

for i in range(N):
  S += A[i]
  
if S < x:
  print(N-1)
else:
  for i in range(N):
    b = x - A[i]
    if b > 0:
      c += 1
      x -= A[i]
    elif b == 0:
      count += 1  
      break
    else:
      break
  print(c)


### FIXED CODE ###

N,x = map(int, input().split())
A = sorted(map(int, input().split()))

S = 0
c = 0

for i in range(N):
  S += A[i]
  
if S < x:
  print(N-1)
else:
  for i in range(N):
    b = x - A[i]
    if b > 0:
      c += 1
      x -= A[i]
    elif b == 0:
      c += 1  
      break
    else:
      break
  print(c)
num = input()
a = 100
count = 0
while count>=0:
  a = a * 1.1
  count = count + 1
  if a>=num:
    break
print(count)

### FIXED CODE ###

num = input()
a = 100
count = 0
while count>=0:
    a = int(a * 1.01)
    count = count + 1
    if a>=int(num):
        break
print(count)
import math

a, b, c, d = map(int, input().split())
g = int(c * d / math.gcd(c, d))
print((b - b // c - b // d + b // g) - ((a-1) - (a-1) // c - (a-1) // d + (a-1) // g))


### FIXED CODE ###

from fractions import gcd

a, b, c, d = map(int, input().split())
g = int(c * d / gcd(c, d))
print((b - b // c - b // d + b // g) - ((a-1) - (a-1) // c - (a-1) // d + (a-1) // g))
arrayNM = list(map(int, input().split()))
array = list(map(int, input().split()))
route = [array[0] + arrayNM[0] - array[arrayNM[1] - 1]]
for i in range(1,arrayNM[1]):
  route.append(array[i] - array[i-1])
  
Max = max(route)
maxIndex = route.index(Max)
distance = 0

for i in range(0,maxIndex):
  distance += route[i]

for i in range(maxIndex, array[0]):
  distance += route[i]

print(distance)
print(route)



### FIXED CODE ###

arrayNM = list(map(int, input().split()))
array = list(map(int, input().split()))
route = [array[0] + arrayNM[0] - array[arrayNM[1] - 1]]
for i in range(1,arrayNM[1]):
  route.append(array[i] - array[i-1])
  
Max = max(route)
maxIndex = route.index(Max)
distance = 0

for i in range(0,maxIndex):
  distance += route[i]

for i in range(maxIndex + 1, arrayNM[1]):
  distance += route[i]

print(distance)
import math
A, B, C, D = map(int, input().split())

def lcm(a,b):
    return a*b/math.gcd(a,b)

b_n = B//C + B//D - B//lcm(C,D)
a_n = (A-1)//C + (A-1)//D - (A-1)//lcm(C,D)
ans_n = b_n - a_n
print(ans_n)
print(B-A+1-ans_n)

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())

def lcm(a,b):
    return a*b//fractions.gcd(a,b)

b_n = B//C + B//D - B//lcm(C,D)
a_n = (A-1)//C + (A-1)//D - (A-1)//lcm(C,D)
ans_n = b_n - a_n
print(int(B-A+1-ans_n))
s = input()
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        print("Bad")
        exit(1)
print("Good")


### FIXED CODE ###

s = input().strip()
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        print("Bad")
        exit()
print("Good")
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]

memo = [[-1] * (tar_w + 1) for i in range(n + 1)]

for i in range(tar_w + 1):
    memo[0][i] = 0


def dp(n, tar_w):
    if memo[n][tar_w] == -1:
        if tar_w < w[n]:
            memo[n][tar_w] = dp(n - 1, tar_w)
        else:
            memo[n][tar_w] = max(dp(n - 1, tar_w), dp(n - 1, tar_w - w[n]) + v[n])
    return memo[n][tar_w]


for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)

for i in range(n):
    ans = dp(i,tar_w)

ans = dp(n, tar_w)

print("{}".format(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
INF = float("inf")
# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]
value_max = 0
for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)
    value_max += v_in


memo = [[-1] * (value_max + 1) for i in range(n + 1)]

for i in range(n + 1):
    memo[i][0] = v[i]

for i in range(value_max + 1):
    memo[0][i] = INF


def dp(i, value):
    if memo[i][value] == -1:
        if value > v[i]:
            rest = dp(i - 1, value - v[i])
            if rest == INF:
                tar = INF
            else:
                tar = rest + w[i]
            memo[i][value] = min(dp(i - 1, value), tar)
        else:
            memo[i][value] = min(dp(i - 1, value), w[i])
    return memo[i][value]


ans = -1
OK_MAX = 0
NG_MIN = value_max + 1

while OK_MAX + 1 != NG_MIN:
    i = int((OK_MAX + NG_MIN) / 2)
    ans_tmp = dp(n, i)
    if ans_tmp <= tar_w:
        OK_MAX = i
    else:
        NG_MIN = i

ans = OK_MAX

print("{}".format(ans))
import sys, re

def echo(A):
    for i, a in enumerate(A):
        if i < len(A) - 1:
            sys.stdout('%d ' % a)
        else:
            sys.stdout('%d\n' % a)

def insertionSort(A, N):
    echo(A)
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = v
        echo(A)


n = int(raw_input())
a_text = raw_input()
splits = re.split(' ', a_text)
a = []
for i, s in enumerate(splits): 
    if s:
        a.append(int(s))

insertionSort(a, n)

### FIXED CODE ###

import sys, re

def echo(A):
    for i, a in enumerate(A):
        if i < len(A) - 1:
            sys.stdout.write('%d ' % a)
        else:
            sys.stdout.write('%d\n' % a)

def insertionSort(A, N):
    echo(A)
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = v
        echo(A)


n = int(raw_input())
a_text = raw_input()
splits = re.split(' ', a_text)
a = []
for i, s in enumerate(splits): 
    if s:
        a.append(int(s))

insertionSort(a, n)
N,X = map(int,input().split())
def lb(N):
    if N != 0:
        return 2*lb(N-1)+3
    else:
        return 1
def pn(N):
    if N != 0:
        return 2*pn(N-1)+1
    else:
        return 1
def B(N,X):
    if X == 0:
        return 0
    elif lb(N-1)+1 >= X:
        return B(N-1,X-1)
    else:
        return pn(N-1)+1+B(N-1,X-lb(N-1)-2)
print(B(N,X))

### FIXED CODE ###

N,X = map(int,input().split())
def lb(N):
    if N != 0:
        return 2*lb(N-1)+3
    else:
        return 1
def pn(N):
    if N != 0:
        return 2*pn(N-1)+1
    else:
        return 1
def B(N,X):
    if X == 0:
        return 0
    elif N == 0:
      	return 1
    elif lb(N-1)+1 >= X:
        return B(N-1,X-1)
    else:
        return pn(N-1)+1+B(N-1,X-lb(N-1)-2)
print(B(N,X))
x,y = map(int, input().split())
if x%y==0
  print(-1)
else:
  print(x)

### FIXED CODE ###

x,y = map(int, input().split())
if x%y==0:
  print(-1)
else:
  print(x)
(n, x) = [int(i) for i in input().split()]
count = 0
for a in range(1,n+1):
    for b in range(a+1,n+1):
        for c in range(b+1, n+1):
            if n = x = 0:
                break
            elif a + b + c == 9:
                count += 1
print(count)

### FIXED CODE ###

while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x == 0:
        break
    count = 0
    for a in range(1,n+1):
        for b in range(a+1,n+1):
            for c in range(b+1, n+1):
                if a + b + c == x:
                    count += 1
    print(count)
a=list(input().split())
b=list(input(),split())
c=int(a[0])
d=int(a[1])
e=int(b[0])
f=int(b[1])
g=c*d-d*e-c*f+e*f
print(g)

### FIXED CODE ###

a=list(input().split())
b=list(input().split())
c=int(a[0])
d=int(a[1])
e=int(b[0])
f=int(b[1])
g=c*d-d*e-c*f+e*f
print(g)
def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    from bisect import bisect_left,bisect
    n = int(input())
    x = list(map(int,input().split()))
    t = n.bit_length()

    kprv = [[10**10 for i in range(t+1)] for j in range(n)]
    for i in range(t):
        for j in range(n):
            if j + pow(2,i) > n-1:
                break
            kprv[j][i] = x[j+pow(2**i)] - x[j]

    L = int(input())
    q = int(input())

    for _ in range(q):
        a , b = map(lambda x:int(x)-1,input().split())
        cou = 0
        if a > b:
            a , b = b , a
        now = a
        while now < b:
            cou += 1
            p = L
            while True:
                nex = bisect(kprv[now],p)
                if nex == 0:
                    break
                else:
                    p -= kprv[now][nex-1]
                    now += pow(2,nex-1)
        print(cou)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)
n = int(input())
a = n//2
ans = 0
for j in range(1,n+1):
    count = 1
    for i in range(a):
        if n % i == 0:
            count += 1
        if count >= 8:
            ans +=1
print(ans)


### FIXED CODE ###

n = int(input())
a = n//2
ans = 0
for j in range(1,n+1):
    count = 0
    for i in range(1,j+1):
        if j % i == 0:
            count += 1
        if count >= 8 and j % 2 == 1:
            ans +=1
print(ans)
operas=input().split(" ")

while len(operas)>1:
    i=0
    while i<len(operas):
        try:
            operas[i]=int(operas[i])
        except ValueError:
            if operas[i]=="+":
                operas[i]=int(operas[i-2])+int(operas[i-1])
            elif operas[i]=="-":
                operas[i]=int(operas[i-2])-int(operas[i-1])
            else:
                operas[i]=int(operas[i-2])*int(operas[i-1])
            operas.pop(i-2)
            operas.pop(i-2)
        i+=1

print(operas[0])
            

### FIXED CODE ###

S = input().split(" ")
stack=[]

while len(S)>1:
    for s in S:
        if s=="+":
            s1=stack.pop(-1)
            s2=stack.pop(-1)
            stack.append(s1+s2)
        elif s=="-":
            s1=stack.pop(-1)
            s2=stack.pop(-1)
            stack.append(s2-s1)
        elif s=="*":
            s1=stack.pop(-1)
            s2=stack.pop(-1)
            stack.append(s1*s2)
        else:
            stack.append(int(s))
    S=stack
print(S[0])
def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


dfs(0, -1)
print(*counter)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


dfs(0, -1)
print(*counter)
import math
a,b,c,d = map(int,input().split())

c_m = b//c - (-(-a//c)) +1
d_m = b//d  - (-(-a//d)) + 1
cd = c*d//math.gcd(c,d)
cd_m = b//(cd) - (-(-a//(cd))) + 1

print(b-a+1 -(c_m + (d_m -cd_m)*(d%c != 0)))

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

c_m = b//c - (-(-a//c)) +1
d_m = b//d  - (-(-a//d)) + 1
cd = lcm(c,d)
cd_m = b//(cd) - (-(-a//(cd))) + 1

print(b-a+1 -(c_m + (d_m -cd_m)*(d%c != 0)))
n= int(input())
s=[]
for i in range(n):
  s.append(int(input()))
  
print(set(s))

### FIXED CODE ###

n= int(input())
s=[]
for i in range(n):
  s.append(input())
  
print(len(set(s)))
import argparser

def prime_calc(n):
    if n < 2:
        return 0
    else:
        i = 2
        while i*i <= n:
            if n % i == 0:
                return 0
            else:
                i = i + 1

    return 1

def prime(n):
    cnt = 0
    for i in range(1, n+1):
        ans = prime_calc(i)
        if ans == 1:
           cnt = cnt + 1

    return cnt

def main():
    l = []
    
    parser = argparse.ArgumentParser()
    parser.add_argument("filename", help="The filename to be processed")
    args = parser.parse_args()

    if args.filename:
        with open(args.filename) as f:
            for line in f:
                a = int(line.rstrip())
                l.append(a)


    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

if __name__ == "__main__":
    main()