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

'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    update = True
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = False
    if update:
        print(- d[V - 1])
        exit()

for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

if negative[V - 1]:
    print('inf')
else:
    print(- d[V - 1])

### FIXED CODE ###

'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

if negative[V - 1]:
    print('inf')
else:
    print(- d[V - 1])
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
A.sort()
for _ in range(M):
    B, C = map(int,input().split())
    if A[B - 1] <= C:
        A[:B] = [C] * B
        A.sort()
    else:
        A[:B] = np.maximum(A[:B], C)
print(np.sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(N):
    if A[i] >= BC[j][1]:
        break
    else:
        A[i] = BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j += 1
        if j >= M:
            break
print(sum(A))
### BUGGY CODE ###

N, K = map(int, input().split())
P = input().split()
P = [int(p) for p in P]

import numpy as np

E = (np.array(P)+1)/2

ans = 0.0
for i in range(K,N+1):
  if sum(E[i-K:i])> ans:
    ans = sum(E[i-K:i])
print(float(ans))

### FIXED CODE ###

N, K = map(int, input().split())
P = input().split()
P = [int(p) for p in P]

import numpy as np

E = (np.array(P)+1)/2
E = np.cumsum(E)  

ans = E[K-1]
for i in range(0,N-K):
  ans = max(ans, E[i+K]-E[i])
print(float(ans))
### BUGGY CODE ###

n = int(input())
ans = 1
A = list(map(int,input().split()))
for x in A:
  ans *= x
if ans > 10**18:
  print(-1)
  exit(0)
print(ans)


### FIXED CODE ###

n = int(input())
ans = 1
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  exit(0)
for x in A:
  ans *= x
  if ans > 10**18:
    print(-1)
    exit(0)
print(ans)
### BUGGY CODE ###

import math
z = range(1, 1+int(input()))
y = 0
for a in z:
  for b in z:
    for c in z:
      y += math.gcd(math.gcd(a,b),c)
print(y)

### FIXED CODE ###

from math import gcd
z = range(1, 1+int(input()))
y = 0
for a in z:
  for b in z:
    for c in z:
      y += gcd(gcd(a,b),c)
print(y)
### BUGGY CODE ###

N,P=map(int,input().split())
S=list(map(int,list(input())))
count=0

if P!=2 and P!=5:
    for i in range(0,N):
        chec=S[i]
        j=0
        while i+j<N:
            chec%=P
            if chec==0:
                count+=1
            j+=1
            if i+j<N:
                chec=chec*10+S[i+j]
if P==2:
    for i in range(N):
        if S[i]%2==0:
            count+=i+1
if P==5:
    for i in range(N):
        if S[i]==0 or S[i]==5:
            count+=i+1
print(count)


            




### FIXED CODE ###

#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)
### BUGGY CODE ###

import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D_origin = {}
for i in range(N):
    D_origin.update({C[i]:0})
D = dict(D_origin)
E = [{0:0}] * N
for i in range(N):
    D[C[i]] += 1
    D_other = dict(D)
    E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = dict(E[R[i] - 1].items() - D_origin.items())
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    ans = len(E_dif.values())
    print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

def main():
    n, m = map(int, input().split())
    query = []
    result =  [[] for i in range(n)]
    for i in range(m):
        qList = list(map(int, input().split()))
        query.append(qList)
        result[qList[0]-1].append(qList[1])

    for i in result:
        i.sort()

    for city in query:
        rank = result[city[0]-1].index(city[1])+1
        resultStr = "{}{}".format(str(city[0]).zfill(6), str(rank).zfill(6))
        print(resultStr)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
def calc(A,B):
  res = [[0]*n for i in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += A[i][k] * B[k][j]
      res[i][j] %= mod
  return res


def power(A,k):
  if k == 1:
    return A
  elif k % 2 == 0:
    tmp = power(A,k//2)
    return calc(tmp,tmp)
  elif k % 2 == 1:
    return calc(A,power(A,k-1))

result = power(A,k)
print(sum(map(sum,result))%mod)
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
def calc(A,B):
  res = [[0]*n for i in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += A[i][k] * B[k][j]
      res[i][j] %= mod
  return res


def power(A,k):
  if k == 1:
    return A
  elif k % 2 == 0:
    tmp = power(A,k//2)
    return calc(tmp,tmp)
  elif k % 2 == 1:
    return calc(A,power(A,k-1))

result = power(A,k)
print(sum(map(sum,result))%mod)
### BUGGY CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return x|y

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

### FIXED CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
        
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            S[int(a)-1] = b
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()
### BUGGY CODE ###

K = int(input())

n = 7
ans = 0
i = 1
if K%2==0:
    ans = -1
else:
    while True:
        if n%K==0:
            ans = i
            break
        n *= 10
        n += 7
        n %= K
        i += 1
print(ans)

### FIXED CODE ###

K = int(input())

n = 7
ans = -1
i = 1
if K%2==0:
    ans = -1
else:
    for i in range(K*2+10):
        if n%K==0:
            ans = i+1
            break
        n *= 10
        n += 7
        n %= K
print(ans)
### BUGGY CODE ###

import numpy as np
import copy

n, m = map(int, input().split())

lis_raw = [[10000000 for i in range(n)] for j in range(n)]
lis = np.array(lis_raw)
hen = []
for _ in range(m):
    hen.append(list(map(int, input().split())))

ans = 0
for x in range(m):
    lis_tmp = copy.deepcopy(lis)
    bri = copy.deepcopy(hen)
    bri.pop(x)
    for y in range(m-1):
        lis_tmp[bri[y][0]-1][bri[y][1]-1] = 1
        lis_tmp[bri[y][1]-1][bri[y][0]-1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                lis_tmp[i][j] = min(lis_tmp[i][j], lis_tmp[i][k] + lis_tmp[k][j])

    if 10000000 in lis_tmp:
        ans += 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
hen = []
for _ in range(m):
    hen.append(list(map(int, input().split())))

def dfs(vis, graph, x, n):
    vis[x] = True
    for i in range(n):
        if graph[x][i] == False:
            continue
        if vis[i] == True:
            continue
        dfs(vis, graph, i, n)
    return vis


ans = 0
for i in range(m):
    graph = [[False for _ in range(n)] for _ in range(n)]
    rng = [a for a in range(m)]
    del rng[i]
    for y in rng:
        graph[hen[y][0]-1][hen[y][1]-1] = True
        graph[hen[y][1]-1][hen[y][0]-1] = True
    vis = [False for _ in range(n)]
    vis = dfs(vis, graph, 0, n)
    connected = True
    for k in range(n):
        if vis[k] == False:
            connected = False
    if connected == False:
        ans += 1

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

N, X = [int(i) for i in input().split()]
sList = [int(i) for i in input().split()]
sList.sort(reverse=True)
mod = 10 ** 9 + 7

dp = [0 for _ in range(X + 1)]
dp[X] = 1
for i, s in enumerate(sList):
    new_dp = [0 for _ in range(X + 1)]
    for x in range(X + 1):
        new_dp[x] += dp[x] * (N - i - 1)
        new_dp[x] %= mod
        new_dp[x % s] += dp[x]
        new_dp[x % s] %= mod
    dp = new_dp

ans = 0
for i in range(len(dp)):
    ans += i * dp[i]
    ans %= mod

print(ans)

### FIXED CODE ###

from collections import defaultdict as dd

N, X = [int(i) for i in input().split()]
sList = [int(i) for i in input().split()]
sList.sort(reverse=True)
mod = 10 ** 9 + 7

dp = dd(int)
dp[X] = 1
for i, s in enumerate(sList):
    new_dp = dd(int)
    for x in dp:
        new_dp[x] += dp[x] * (N - i - 1)
        new_dp[x] %= mod
        new_dp[x % s] += dp[x]
        new_dp[x % s] %= mod
    dp = new_dp

ans = 0
for x in dp:
    ans += x * dp[x]
    ans %= mod

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

N = int(input())
S = []
for i in range(N):
    s = str(input())
    if s not in S:
        S.append(s)

print(len(S))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    s = str(input())
    S.append(s)
S1 = sorted(S)
counter=1
for i in range(N-1):
    if S1[i]!=S1[i+1]:
        counter+=1
print(counter)
### BUGGY CODE ###

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

a = [i for i in range(1,N+1)]
for i in range(M):
    L, R = list(map(int,input().split()))
    aa = [i for i in range(L, R+1)]
    a = set(a) & set(aa)

print(len(a))

### FIXED CODE ###

N, M = map(int, input().split())
maxL, minR = 0, N+1
for i in range(M):
  L, R = map(int, input().split())
  maxL = max(L, maxL)
  minR = min(R, minR)
ans = minR -maxL + 1
print(ans if ans>0 else 0)
### BUGGY CODE ###

n = int(input()) 
a = list(map(int, input().split()))
a2 = sorted(a)
ans = n
for i in range(len(a2)):
  for j in range(len(a2)):
    if i != j or i > j:
      if a2[i] % a2[j] == 0:
        ans -= 1
        break

print(ans)

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)

for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1

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

def D():
    s = input()
    sketa = len(s)
    ans = 0
    mods = {0:1}
    for i in range(1,sketa+1):
        mod = int(s[-i:])%2019
        try:
            ans += mods[mod]    
            mods[mod] += 1
        except KeyError:
            mods[mod] = 1
    print(ans)
D()


### FIXED CODE ###

def D():
    s = input()
    mods = [0]*2019
    mods[0] = 1
    mod = 0
    for i, element in enumerate(s[::-1]):
        mod += int(element)*pow(10,i,2019)
        mods[mod%2019] += 1
    print(sum(map(lambda x:int(x*(x-1)/2), mods)))
D()
### BUGGY CODE ###

n, m = map(int, input().split())
submit = []
for i in range(m):
    p, s = map(str, input().split())
    p = int(p)
    submit.append([p, s])

ACed = set()
for p, s in submit:
    if p in ACed:
        continue
    else:
        if s == "AC":
            ACed.add(p)

A = len(ACed)
P = 0

for i in range(1, n+1):
    if i in ACed:
        count = 0
        for p, s in submit:
            if p == i and s == "WA":
                count += 1
            elif p != i:
                continue
            else:
                break
        P += count

print(A, P)

### FIXED CODE ###

n, m = map(int, input().split())

tasks = []
for i in range(n):
    tasks.append([0, 0])

A = 0
P = 0

for i in range(m):
    p, s = map(str, input().split())
    p = int(p)

    if tasks[p-1][0] == 0:
        if s == "AC":
            A += 1
            tasks[p-1][0] = 1
            P += tasks[p-1][1]
        else:
            tasks[p-1][1] += 1
    else:
        continue

print(A, P)
### BUGGY CODE ###

N, M = map(int, input().split())
paths = []

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
inf_flg = False 

for i in range(N * 2) :
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c and not(cost[t] == cost[f] == INF):
            cost[t] = cost[f] + c
            
            if i >= N and t == N - 1:
                inf_flg = True 
    
if inf_flg == True :
    print("inf")
else :
    for c in cost :
        if c == INF :
            print("")
    print(cost[N - 1])

### FIXED CODE ###

N, M = map(int, input().split())
paths = []

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

for i in range(N) :
    break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            break_flg = False
            
            if i == N - 1 and t == N - 1 :
                inf_flg = True 
            
    # break flg
    if break_flg == True :
        break
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])
### BUGGY CODE ###

import bisect as bi
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ans = 0
for i in range(len(c)):
    for j in range(bi.bisect_left(b,c[i])):
        ans += bi.bisect_left(a,b[j])
print(ans)

### FIXED CODE ###

import bisect as bi
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ans = 0
for i in range(len(b)):
        ans += bi.bisect_left(a,b[i]) *  (len(c) - bi.bisect_right(c,b[i]))
print(ans)
### BUGGY CODE ###

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]

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


def checker(n):
    for i in info[n]:
        if n in info[i]:
            del info[i][info[i].index(n)]
        checker(i)


def plus(n, val):
    ans[n] += val
    for i in info[n]:
        plus(i, val + Query[i])


checker(0)
Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))


### FIXED CODE ###

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
check = [1 for _ in range(N)]

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


def plus(n, val):
    ans[n] += val
    check[n] = 0
    for i in info[n]:
        if check[i]:
            plus(i, val + Query[i])


Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))