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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = {}
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)
  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])
    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

H, N=map(int, input().split())
dp=[0]+[float('inf') for _ in range(2*10**4)]
for _ in range(N):
  a, b=map(int, input().split())
  for i in range(a, H+a):
    dp[i]=min(dp[i-a]+b, dp[i])
    
print(min(dp[H:]))

### FIXED CODE ###

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

nums=[-1]*20001
for i in range(N):
  if nums[AB[i][0]]<0:
    nums[AB[i][0]]=AB[i][1]
  else:
    nums[AB[i][0]]=min(AB[i][1], nums[AB[i][0]])
  
for i in range(1, H):
  if nums[i]>0:
    for j in range(N):
      if nums[i+AB[j][0]]>0:
        if nums[i+AB[j][0]]>nums[i]+AB[j][1]:
          nums[i+AB[j][0]]=nums[i]+AB[j][1]
      else:
        nums[i+AB[j][0]]=nums[i]+AB[j][1]
      
anss=[]
for i in range(H, 20000):
  if nums[i]>0:
    anss.append(nums[i])
    
print(min(anss))
### BUGGY CODE ###

N, M = map(int, input().split())
a_list = list(map(int, input().split()))
written_nums = []

for i in range(M):
    b, c = map(int, input().split())
    written_nums += [c] * b

a_list = sorted(a_list)
written_nums = sorted(written_nums, reverse = True)

max_total = sum(a_list)
total = sum(a_list)
written_len = len(written_nums)
for i in range(min(N, written_len)):
    total -= a_list[i]
    total += written_nums[i]
    max_total = max(max_total, total)

print(max_total)


### FIXED CODE ###

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

written_nums = []
for i in range(M):
    b, c = map(int, input().split())
    written_nums.append((c, b))

written_nums.sort(reverse = True)
append_list = []
for c, b in written_nums:
    append_list += [c for _ in range(b)]

    if len(append_list) >= N:
        break

a_list += append_list
a_list.sort(reverse = True)

print(sum(a_list[:N]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]
        self.is_leaf = [0]*n

        def dfs(p,v,d):
            self.dep[v]=d
            self.par[0][v]=p
            f = True
            for w in l[v]:
                if w!=p:
                    dfs(v,w,d+1)
                    f = False
            if f:
                self.is_leaf[v] = 1
        dfs(-1,start,0)
        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

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

LCA = LCA1(G, v)
ans = 0
for i in range(n):
    if not LCA.is_leaf[i]:
        continue
    lca = LCA.lca(u, i)
    if lca == v:
        continue
    if LCA.dist(lca, u) >= LCA.dist(lca, v):
        continue
    turn = 0
    tmp = 0
    d = LCA.dist(u, lca) + LCA.dist(lca, i)
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = LCA.dep[i]
    m = tak-aoki
    if m%2==1:
        tmp += 2*m -1
    else:
        tmp += 2*(m-1)
    ans = max(ans, tmp)
print(ans//2)


### FIXED CODE ###

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

from collections import deque

def main():
    n, u, v = map(int, input().split())
    u, v = u-1, v-1
    G = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int, input().split())
        a,b = a-1,b-1
        G[a].append(b)
        G[b].append(a)

    def bfs(start):
        dist = [0]*n
        is_leaf = [0]*n
        que = deque()
        que.append((start, -1, 0))
        while que:
            c,p,d = que.pop()
            dist[c] = d
            cnt = 0
            for to in G[c]:
                if to != p:
                    que.append((to,c,d+1))
                    cnt += 1
            if not cnt:
                is_leaf[c] = 1
        return dist, is_leaf

    a, is_leaf = bfs(v)
    b, _ = bfs(u)

    ans = 0
    for i in range(n):
        if not is_leaf[i]:
            continue
        if b[i] >= a[i]:
            continue
        tmp = 0
        d = b[i]
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = a[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

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

from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    altitutes = load_data()

    edges = create_edges(altitutes)

    areas = calc_areas(altitutes, edges)

    print(int(sum(areas)))
    print(*([len(areas)] + [*map(int, areas)]))

def load_data():
    A = [0]
    for s in stdinput():
        if s == '\\':
            A.append(A[-1] - 1)
        elif s == '_':
            A.append(A[-1])
        elif s == '/':
            A.append(A[-1] + 1) 
    return A

def create_edges(A):
    edges = []
    n = len(A)
    i = 0
    while i < n - 1:
        j = i + 1
        while  j < n and A[i] > A[j]:
            j += 1
        if j == n:
            j = i + 1
        edges.append([i, j])
        i = j
    return edges

def calc_areas(A, edges):
    areas = []

    for begin, end in edges:
        area = calc_area(A, begin, end)
        if area > 0:
            areas.append(area)
    return areas

def calc_area(A, begin, end):
    if A[begin] != A[end]:
        return 0
    b_level = A[begin]
    area = 0
    for l1, l2 in zip(range(begin, end), range(begin+1, end + 1)):
        a1 = A[l1]
        a2 = A[l2]
        area += (b_level - a1 + b_level - a2) * 1 / 2
    return area

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')


### FIXED CODE ###

from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    altitutes = load_data()

    edges = create_edges(altitutes)

    # print(*edges)

    areas = calc_areas(altitutes, edges)

    print(int(sum(areas)))
    print(*([len(areas)] + [*map(int, areas)]))

def load_data():
    A = [0]
    for s in stdinput():
        if s == '\\':
            A.append(A[-1] - 1)
        elif s == '_':
            A.append(A[-1])
        elif s == '/':
            A.append(A[-1] + 1) 
    return A

def create_edges(A):
    st = [(0, None, 0)]
    highest = 0
    for i, a in enumerate(A[1:], 1):
        if st[-1][0] >= a:
            st.append((a, st[-1][2], i))
        else:
            begin = i - 1
            # NOTE: concat edges
            # this operation is performed every upforward(/) step,
            # and previous concated edges have altitute of (a - 1).
            while st[-1][1] != None and st[-1][0] == a - 1 and highest >= a:
                lev, begin, j = st.pop()
            highest = max(highest, a)
            st.append((a, begin, i))
        # print(*st)
    return [*map(lambda e: e[1:], st[1:])]

def calc_areas(A, edges):
    areas = []
    for begin, end in edges:
        area = calc_area(A, begin, end)
        if area > 0:
            areas.append(area)
    return areas    

def calc_area(A, begin, end):
    if A[begin] != A[end]:
        return 0
    b_level = A[begin]
    area = 0
    for l1, l2 in zip(range(begin, end), range(begin+1, end + 1)):
        a1 = A[l1]
        a2 = A[l2]
        area += (b_level - a1 + b_level - a2) * 1 / 2
    return area

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')
### BUGGY CODE ###

import collections

num_of_numbers = int(input())
numbers = list(map(int, input().split()))
num_of_operation = int(input())

# intで初期化するため0が返る
cnt = collections.defaultdict(int)
# numbersに含まれる各数字の出現回数を保持
for i in set(numbers):
    cnt[i] = numbers.count(i)
# 初期状態の和を算出
ans = sum(numbers)

for i in range(num_of_operation):
    B, C = map(int, input().split())

    # 置換対象の数字が存在する場合
    if B in cnt:
        tmpB = cnt[B]
        tmpC = cnt[C]
        ans = ans - (B * tmpB) + (C * tmpB)

        cnt[C] = tmpC + tmpB
        cnt.pop(B)

    print(ans)




### FIXED CODE ###

import collections

num_of_numbers = int(input())
numbers = list(map(int, input().split()))
num_of_operation = int(input())

# intで初期化するため0が返る
cnt = collections.defaultdict(int)
# numbersに含まれる各数字の出現回数を保持
for i in numbers:
    cnt[i] += 1

# 初期状態の和を算出
ans = sum(numbers)

for i in range(num_of_operation):
    B, C = map(int, input().split())

    # 置換対象の数字が存在する場合
    if B in cnt:
        tmpB = cnt[B]
        tmpC = cnt[C]
        ans = ans - (B * tmpB) + (C * tmpB)

        cnt[C] = tmpC + tmpB
        cnt.pop(B)

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

n = int(input())

s = []
for _ in range(n):
    s.append(input())
s = s + s

def check(a):
    flag = True
    n = len(a)
    for i in range(n):
        for j in range(n):
            if a[i][j] == a[j][i]:
                pass
            else:
                flag = False
    return flag

ans = 0
for i in range(n):
    if check(s[i:i+n]):
        ans += n
    else:
        pass
print(ans)

### FIXED CODE ###

n = int(input())

s = []
for _ in range(n):
    s.append(input())
s = s + s

def check(a):
    flag = True
    n = len(a)
    i, j_start = 0, 1
    while flag:
        if i == n - 1:
            break
        for j in range(j_start, n):
            if a[i][j] != a[j][i]:
                flag = False
        i += 1
        j_start += 1
    return flag

ans = 0
for i in range(n):
    if check(s[i:i+n]):
        ans += n
    else:
        pass
print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
stack, seen = deque(["0"]), deque([])
c = 0
while stack:
  x = stack.pop()
  seen.append(x)
  if int(x)>N:
    continue
  if all(x.count(i)>0 for i in "753"):
    c += 1
  for i in "753":
    if x+i in seen:
      continue
    else:
      stack.append(x+i)
print(c)

### FIXED CODE ###

import itertools
N = int(input())
A = ["3", "5", "7"]
L = []
for i in range(1, 10):
  for l in itertools.product(A, repeat=i):
    L.append(l)
c = 0
for l in L:
  if int("".join(l))<=N and l.count("3")>=1 and \
  l.count("5")>=1 and l.count("7")>=1:
    c += 1
print(c)
### BUGGY CODE ###

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

cnt=0
for i in range(n):
    for j in range(i+1,n):
        if l[i] == l[j]:
            cnt += 1
    else:
        continue

if cnt == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
cnt=0
for i in range(len(l)):
    if i == 0:
        continue
    elif l[i]==l[i-1]:
        cnt+=1

if cnt == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

S = list(input())
N = len(S)
 
 
l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * 10**index
    l[temp%2019] += 1
    index += 1
 
ans = l[0]
 
for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2
 
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
S = [int(s) for s in S]
S = S[::-1]
l = [0] * 2019
index = 0
tmp = 0
z = 1
for i, s in enumerate(S):
    tmp += s * pow(10, i, 2019)
    l[tmp%2019] += 1

ans = l[0]

for v in l:
    ans += v * (v-1) // 2
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
M = np.arange(1,N+1)
ls = []
for i in range(1,N+1):
    ls.append(M[A==i][0])
print(*ls)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [None] * N
for i,a in enumerate(A):
    ans[a-1] = i + 1
print(*ans)
### BUGGY CODE ###

from collections import Counter

N = int(input())

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

Q = int(input())

BC = []
for _ in range(Q):
    b, c = map(int, input().split())
    BC.append([b, c])

C = Counter(A)
for bc in BC:
    b = bc[0]
    c = bc[1]
    if b in C:
        if c in C:
            C[c] += C[b]
            C[b] = 0
        else:
            C[c] = C[b]
            C[b] = 0
    print(sum([k*v for k, v in C.items()]))


### FIXED CODE ###

from collections import Counter

N = int(input())

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

Q = int(input())

BC = []
for _ in range(Q):
    b, c = map(int, input().split())
    BC.append([b, c])

C = Counter(A)
S = sum([k*v for k, v in C.items()])
for bc in BC:
    b = bc[0]
    c = bc[1]
    if b in C:
        bf = C[b]
        S += (c-b) * bf
        if c in C:
            C[c] += C[b]
            C[b] = 0
        else:
            C[c] = C[b]
            C[b] = 0
    print(S)
### BUGGY CODE ###

def isok(a):
    for j in range(21):
        if(a>>j&1):
            if(bit[j]>0):
                return False
    return True
def bitplus(a):
    for j in range(21):
        if(a>>j&1):
            bit[j]+=1
def bitdif(a):
    for j in range(21):
        if(a>>j&1):
            bit[j]-=a>>j&1

N=int(input())
A=list(map(int,input().split()))
left=0
ans=0
bit=[0]*21
right=0
while(left<N):
    while(right<N and isok(A[right])):
        bitplus(A[right])
        right+=1
    ans+=right-left
    if right==left:
        right+=1
    else:
        bitdif(A[left])
    left+=1
print(ans)

### FIXED CODE ###

def isok(a):
    for j in range(21):
        if(a>>j&1):
            if(bit[j]>0):
                return False
    return True
def bitplus(a):
    for j in range(21):
        if(a>>j&1):
            bit[j]+=1
def bitdif(a):
    for j in range(21):
        if(a>>j&1):
            bit[j]-=a>>j&1

N=int(input())
A=list(map(int,input().split()))
left=0
ans=0
bit=[0]*21
right=0
while(left<N):
    while(right<N and isok(A[right])):
        bitplus(A[right])
        right+=1
    ans+=right-left
    if right==left:
        right+=1
    else:
        bitdif(A[left])
    left+=1
print(ans)
### BUGGY CODE ###

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

dp = [[None for _ in range(W+1)] for _ in range(N+1)]
dp[0] = [0]*(W+1)

for i in range(1, N+1):
    for j in range(W+1):
        if Data[i-1][0] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-Data[i-1][0]] + Data[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[-1]))


### FIXED CODE ###

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

dp = [[None for _ in range(W+1)] for _ in range(N+1)]
dp[0] = [0]*(W+1)

for i in range(1, N+1):
    for j in range(W+1):
        if Data[i-1][0] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-Data[i-1][0]] + Data[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[-1]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

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

from collections import deque
N = int(input())
S = []
for _ in range(N):
  S.append(input())
  
G = [[] for _ in range(N)]
for i in range(N):
  for j in range(i+1,N):
    if S[i][j] == '1':
      G[i].append(j)
      G[j].append(i)

# 2部グラフ判定
visited = [False] * N
willSearch = [False] * N
Color = [-1] * N
Q = deque()
Q.append((0,0))
while Q:
  now, c = Q.pop()
  visited[now] = True
  Color[now] = c
  for nxt in G[now]:
    if Color[nxt] >= 0 and c == Color[nxt]:
      #隣接色が一致してしまった
      print(-1)
      exit(0)
    if visited[nxt] or willSearch[nxt]:
      continue
    Q.append((nxt,1-c)) # 1-cで0/1を交換
    willSearch[nxt] = True
    
INF = 1000
D = [[INF for _ in range(N) ]  for _ in range(N)]
for i in range(N):
  for nxt in G[i]:
    D[i][nxt] = 1
    D[nxt][i] = 1
    
#Warshall-Floyd
for k in range(N):
  for i in range(N):
    for j in range(N):
      #print(i,j,k)
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      
#print(*D, sep="\n")

ans = 0
for i in range(N):
  for j in range(i+1,N):
    ans = max(ans, D[i][j])
    
print(ans+1)

### FIXED CODE ###

from collections import deque
N = int(input())
S = []
for _ in range(N):
  S.append(input())
  
G = [[] for _ in range(N)]
for i in range(N):
  for j in range(i+1,N):
    if S[i][j] == '1':
      G[i].append(j)
      G[j].append(i)

# 2部グラフ判定
visited = [False] * N
willSearch = [False] * N
Color = [-1] * N
Q = deque()
Q.append((0,0))
while Q:
  now, c = Q.pop()
  visited[now] = True
  Color[now] = c
  for nxt in G[now]:
    if Color[nxt] >= 0 and c == Color[nxt]:
      #隣接色が一致してしまった
      print(-1)
      exit(0)
    if visited[nxt] or willSearch[nxt]:
      continue
    Q.append((nxt,1-c)) # 1-cで0/1を交換
    willSearch[nxt] = True
    
INF = 1000
D = [[INF for _ in range(N) ]  for _ in range(N)]
for i in range(N):
  for nxt in G[i]:
    D[i][nxt] = 1
    D[nxt][i] = 1
    
#Warshall-Floyd
for k in range(N):
  for i in range(N):
    for j in range(N):
      #print(i,j,k)
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      
#print(*D, sep="\n")

ans = 0
for i in range(N):
  for j in range(i+1,N):
    ans = max(ans, D[i][j])
    
print(ans+1)
### BUGGY CODE ###

a = int(input())
A = [int(i) for i in input().split()]
total = 1
for i in A:
    total *= i
if total > 10**18:
    total = -1
print(total)

### FIXED CODE ###

a = int(input())
A = [int(i) for i in input().split()]
total = 1
for i in A:
    if total != -1:
        total *= i
        if total > 10**18:
            total = -1
    else:
        if i==0:
            total = 0
            break
print(total)
### BUGGY CODE ###

def main():
  join = ''.join
  def getCharNGram(n,s):
      charGram = (join(s[i:i+n]) for i in range(len(s)-n+1))
      return charGram
  N = int(input())
  S = input()
  ans = 0
  from collections import Counter
  for i in range(1,N//2+1):
      l = getCharNGram(i,S)
      am = Counter(l)
      for j in am.values():
        if j>1:
          ans =max(i,ans)
  print(ans)
main()

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
res = 0
for i in range(N-1,-1,-1):
  for j in range(N-1,i,-1):
    if S[i]==S[j]:
      dp[i][j]=max(dp[i+1][j+1]+1,dp[i][j])
    res = max(res,min(j-i,dp[i][j]))
print(res)
### BUGGY CODE ###

if __name__=='__main__':
    n,k,*h=map(int,open(0).read().split())
    dp=[0]
    for i in range(1,n):
        t=h[i]
        d=10**18
        for v,w in zip(dp[max(0,i-k):i],h[max(0,i-k):i]):
            d=min(d,v+abs(t-w))
        dp.append(d)
    print(dp[-1])

### FIXED CODE ###

n,k,*h=map(int,open(0).read().split())
dp=[0]+[10**18]*~-n
for i in range(1,n):
    for j in range(k):
        if i-k+j<0:continue
        dp[i]=min(dp[i],dp[i-k+j]+abs(h[i]-h[i-k+j]))
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = [None]
for j in range(n):
    a.append(int(input()))

i = 1
c = 0
r = [1]
while True:
    c += 1
    i = a[i]
    if i == 2:
        print(c)
        break
    else:
        if i in r:
            print(-1)
            break
        else:
            r.append(i)

### FIXED CODE ###

n = int(input())
a = [None]
for j in range(n):
    a.append(int(input()))

i = 1
c = 0
r = [1]
while True:
    c += 1
    i = a[i]
    if i == 2:
        print(c)
        break
    if c > (10**5):
        print(-1)
        break
### BUGGY CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
qlist = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    qlist[p-1] += x

    
cnt = [-1]*N
q = [qlist[0]]
cnt[0] = qlist[0]
g = 10**10
while q:
    temp = q.pop(0)
    v = temp//g
    c = temp%g
    for i in L[v]:
        if cnt[i] < 0:
            q.append(i*g + c+qlist[i])
            cnt[i] = c+qlist[i]
            
for i in range(N):
    cnt[i] = str(cnt[i])
print(" ".join(cnt))

### FIXED CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
while q:
    temp = q.pop()
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)