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

import sys
class BinaryTree:
    def __init__(self):
        self.root = None
    def b_insert(self,x):
        self.root = insert(self.root,x)
    def b_inorder(self):
        return inorder(self.root)
    def b_preorder(self):
        return preorder(self.root)
        
class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None
            
def insert(node,x):
    if node is None:
        return Node(x)
    elif x == node.data:
        return node
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node
def inorder(node):
    nodelist = []
    if node.left:
        nodelist += inorder(node.left)
    nodelist += [node.data]
    if node.right:
        nodelist += inorder(node.right)
    return nodelist
def preorder(node):
    nodelist = [node.data]
    if node.left:
        nodelist += preorder(node.left)
    if node.right:
        nodelist += preorder(node.right)
    return nodelist

line = sys.stdin.readline()
bfs = BinaryTree()

for temp in sys.stdin:
    if temp[0] == 'i':
        command,num = (n for n in temp.split(" "))
        bfs.b_insert(int(num))
    else:
        print("",end=" ")
        print(*bfs.b_inorder())
        print("",end=" ")
        print(*bfs.b_preorder())

### FIXED CODE ###

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, x):
        node = self.Node(x)
        if self.root is None:
            self.root = node
        else:
            here = self.root
            #
            temp = None
            while here is not None:
                temp = here
                if x < here.node:
                    here = here.left
                elif x > here.node:
                    here = here.right
            if x < temp.node:
                temp.left = node
            elif x > temp.node:
                temp.right = node

    def inorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        self.inorder(answer, address.left)
        answer.append(address.node)
        self.inorder(answer, address.right)

    def preorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        answer.append(address.node)
        self.preorder(answer, address.left)
        self.preorder(answer, address.right)

    class Node:
        def __init__(self, x):
            self.node = x
            self.left = None
            self.right = None

query = int(input())
bt = BinarySearchTree()
for _ in range(query):
    command = input()
    if command[0] == "i":
        bt.insert(int(command.split(" ")[1]))
    else:
        a = []
        bt.inorder(a)
        print(" ", end = "")
        print(*a)
        a = []
        bt.preorder(a)
        print(" ", end = "")
        print(*a)
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    roop=0
    iti=0
    rirekin=0
    rireki=[]
    while roop==0:
        iti=a[iti]-1
        if iti in rireki:
            mae=rireki.index(iti)
            Mae=rireki[:mae]
            del rireki[:mae]
            roop=rirekin-mae
            break
        rireki.append(iti)
        rirekin+=1
    if k <= mae:
        print(Mae[k-1]+1)
    else:
        k-=mae
        print(rireki[(k%roop)-1]+1)
resolve()

### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    check=[-1]*n
    iti=0
    rireki=[]
    while True:
        iti=a[iti]-1
        if check[iti]==0:
            mae=rireki.index(iti)
            Mae=rireki[:mae]
            Loop=rireki[mae:]
            roop=len(Loop)
            break
        rireki.append(iti)

        check[iti]=0
    if k <= mae:
        print(Mae[k-1]+1)
    else:
        k-=mae
        print(Loop[(k%roop)-1]+1)
resolve()
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

c = []
for i in range(m):
  c.append([u[i]-1,v[i]-1,a[i]])
  c.append([v[i]-1,u[i]-1,a[i]])

from heapq import heappop, heappush
inf=float('inf')
d=[inf for _ in range(n)]
d[s-1]=0
prev=[None]*n
p=dict()
for i,j,k in c: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[s-1],s-1))
while q:
  du, u1 = heappop(q)
  if d[u1]<du: continue
  for v1,weight in p.get(u1,[]):
    alt=du+weight
    if d[v1]>alt:
      d[v1]=alt
      prev[v1]=u1
      heappush(q, (alt,v1))

c2 = []
for i in range(m):
  c2.append([u[i]-1,v[i]-1,b[i]])
  c2.append([v[i]-1,u[i]-1,b[i]])

d2=[inf for _ in range(n)]
d2[t-1]=0
prev=[None]*n
p=dict()
for i,j,k in c2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d2[t-1],t-1))
while q:
  du, u2 = heappop(q)
  if d2[u2]<du: continue
  for v2,weight in p.get(u2,[]):
    alt=du+weight
    if d2[v2]>alt:
      d2[v2]=alt
      prev[v2]=u2
      heappush(q, (alt,v2))

ans = [d[n-1]+d2[n-1]]
for i in range(1,n):
  ans.append(min(ans[i-1],d[n-1-i]+d2[n-1-i]))

for i in range(n):
  print(10**15-ans[n-1-i])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

for i in ans[::-1]:
  print(10**15-i)
### BUGGY CODE ###

import itertools

N,M,R = map(int, input().split())
r = map(int, input().split())
l = [[1e9 for i in range(N+1)] for i in range(N+1)]

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

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            t = l[i][k] + l[k][j]
            if l[i][j] > t: l[i][j] = t

ans = 1e9
for a in itertools.permutations(r):
    s = sum(l[i][j] for i,j in zip(a[:-1],a[1:]))
    if ans > s: ans = s

print(ans)


### FIXED CODE ###

import itertools

N,M,R = map(int, input().split())
r = map(int, input().split())
l = [[1e9 for i in range(N+1)] for i in range(N+1)]

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

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            t = l[i][k] + l[k][j]
            if l[i][j] > t: l[i][j] = t

ans = 1e9
for a in itertools.permutations(r):
    s = 0
    for i,j in zip(a[:-1],a[1:]):
        s += l[i][j]
    if ans > s: ans = s

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

# -*- coding: utf-8 -*-
"""
Created on Sun Sep 30 09:02:42 2018
ABC111D
@author: maezawa
"""

n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int, input().split())))
    
#print(xy)
m = 1
parity = sum(xy[0])%2
for point in xy:
    if sum(point)%2 != parity:
        m = -1
        break
if m == -1:
    print(m)
else:
    far = 0
    for point in xy:
        length = sum(list(map(abs, point)))
        if length > far:
            far = length
    if parity == 0:
        ds = [1,1]
    else:
        ds = [1,1,1]
    i = 1
    while i**2 < far:
        ds.append(2**i)
        i += 1
    ds.append(2**i)
    ds.reverse()
    print(len(ds))
    print(*ds, sep=' ')
    for point in xy:
        direction = ''
        point0 = [0,0]
        for arm in ds:
            x = point[0] - point0[0]
            y = point[1] - point0[1]
            if abs(x) > abs (y):
                if x > 0:
                    direction += 'R'
                    point0[0] += arm
                else:
                    direction += 'L'
                    point0[0] -= arm
            else:
                if y > 0:
                    direction += 'U'
                    point0[1] += arm
                else:
                    direction += 'D'
                    point0[1] -= arm
            #print(point0)
        print(direction)
                    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Sep 30 09:02:42 2018
ABC111D
@author: maezawa
"""
import sys
input = sys.stdin.readline

n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int, input().split())))
    
#print(xy)
m = 1
parity = sum(xy[0])%2
far = 0
for point in xy:
    length = sum(list(map(abs, point)))
    if length > far:
        far = length
    if length%2 != parity:
        m = -1

if m == -1:
    print(m)
else:
    if parity == 0:
        ds = [1,1]
    else:
        ds = [1,1,1]
    i = 1
    while 2**i < far:
        ds.append(2**i)
        i += 1
    ds.append(2**i)
    ds.reverse()
    print(len(ds))
    print(*ds, sep=' ')
    for point in xy:
        direction = ''
        point0 = [0,0]
        for arm in ds:
            x = point[0] - point0[0]
            y = point[1] - point0[1]
            if abs(x) > abs (y):
                if x > 0:
                    direction += 'R'
                    point0[0] += arm
                else:
                    direction += 'L'
                    point0[0] -= arm
            else:
                if y > 0:
                    direction += 'U'
                    point0[1] += arm
                else:
                    direction += 'D'
                    point0[1] -= arm
            #print(point0)
        print(direction)
### BUGGY CODE ###

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

z = []


def func1(x, y):
    global z
    px = -1
    py = -1
    for i, s in enumerate(z):
        if x in s:
            if py > -1:
                c = len(z[py]) * len(z[i])
                z[py] |= z[i]
                del z[i]
                return c
            elif y in s:
                return 0
            else:
                px = i
        elif y in s:
            if px > -1:
                c = len(z[px]) * len(z[i])
                z[px] |= z[i]
                del z[i]
                return c
            else:
                py = i

    if px > -1:
        lx = len(z[px])
        z[px].add(y)
        return lx

    if py > -1:
        lx = len(z[py])
        z[py].add(x)
        return lx

    z.append({x, y})
    return 1


ans = [0] * (M - 1)
p = 0
for k in range(M - 1, 0, -1):
    p += func1(A[k][0], A[k][1])
    ans[k - 1] = p

nall = N * (N - 1) // 2
for a in ans:
    print(nall - a)
print(nall)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

    for a in reversed(ans[:-1]):
        print(a)


main()
### BUGGY CODE ###

s = input()
q = int(input())
rev = 0
for i in range(q):
    query = list(map(str, input().split()))
    if len(query) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if int(query[1]) == 1:
                s = query[2] + s
            else:
                s = s + query[2]
        else:
            if int(query[1]) == 2:
                s = query[2] + s
            else:
                s = s + query[2]
if rev == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

n = int(input())
s = []
S = []
for i,x in enumerate(map(int,input().split())):
    if i % 2 == 0:
        s.append(x)
        for _ in range(len(s)):
            S.append(s.pop())
    if i % 2 == 1:
        S.append(x)
        for _ in range(len(S)):
            s.append(S.pop())
if len(s) > len(S):print(*s,sep=" ")
else: print(*S,sep=" ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n % 2 == 0:
    a = a[::-2]+a[0::2]
else: a = a[::-2] +a[1::2]
print(*a,sep=" ")
### BUGGY CODE ###

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

flag = False
for i in range(len(A)):
    for j in range(i, len(A)):
        if(j+1 < len(A)):
            if(A[i] == A[j+1]):
                #print("%d=%d"%(A[i], A[j]))
                print("NO")
                flag = True
                break
    if flag:
        break

if not flag:
    print("YES")

### FIXED CODE ###

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

A.sort()
# print(A)
flag = False
for i in range(len(A)):
    if(i+1 < len(A)):
        if(A[i] == A[i+1]):
            print("NO")
            flag = True
            break
if(not flag):
    print("YES")
### BUGGY CODE ###

T = input()

n = T.count("?")

ans = ""
count = 0
for i in range(2 ** n):
    S = T
    for j in range(n):
        if ((i >> j) & 1):
            S = S.replace("?", "P", 1)
        else:
            S = S.replace("?", "D", 1)
    tmp = S.count("D") + S.count("PD")
    count = max(count, tmp)
    if count == tmp:
        ans = S

print(ans)

### FIXED CODE ###

T = input()
print(T.replace("?", "D"))
### BUGGY CODE ###

import math
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
b = [[math.log(aa, 2), i] for i, aa in enumerate(a)]

for i in range(m):
    a[max(b)[1]] = int((max(a) / 2) // 1)
    b[max(b)[1]][0] -= 1
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    k = heapq.heappop(a)
    heapq.heappush(a, -int(-(k / 2) // 1))
print(-sum(a))
### BUGGY CODE ###

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

l = []
ans = 0
for i in range(n):
    if x in l:
        d = l.index(x)
        ans += sum(l[:d])
        le = len(l)-d
        count = sum(l[d:])
        n -= d
        ans += count*(n//le)
        n %= le
        for k in range(d,d+n):
            ans += l[k]
        print(ans)
        exit()
    l.append(x)
    x = (x**2)%m

print(sum(l))


### FIXED CODE ###

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

l = []
ans = 0
for i in range(n):
    if x in l:
      
        d = l.index(x)
        ans += sum(l[:d])
        le = len(l)-d
        
        count = sum(l[d:])
        #print(count)
        n -= d
        #print(n)
        ans += count*(n//le)
        n %= le
        #print(n,ans)
        for k in range(d,d+n):
            ans += l[k]

        print(ans)
        exit()
        break
    l.append(x)
    x = (x**2)%m

print(sum(l))
### BUGGY CODE ###

from heapq import heappop, heappush
N,M = map(int, input().split())
AB = []
for i in range(N):
    A,B = map(int, input().split())
    if A<=M:
        AB.append((A,B))
    else:
        N-=1
AB.sort()

Q = []
ans = 0

for i in range(M):
    while AB and AB[0][0] == i+1:
        A,B = AB.pop(0)
        heappush(Q, -B)
    if Q:
        ans -= heappop(Q)
print(ans)

### FIXED CODE ###

from heapq import heapify, heappop, heappush
N,M = map(int, input().split())
AB = []
for i in range(N):
    a,b = map(int, input().split())
    if a<=M:
        AB.append((a,-b))
    else:
        N-=1
AB.sort()

Q = []
heapify(Q)
ans = 0
i = 0

for day in range(M):
    while i<N and AB[i][0] == day+1:
        heappush(Q, AB[i][1])
        i+=1
    if Q:
        ans -= heappop(Q)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

flip = 0
for _ in range(Q):
    q = input().split()
    if q[0] == "1":
        flip += 1
        flip %= 2
    else:
        if (int(q[1]) + flip)%2 == 0:
            S = S + q[2]
        else:
            S = q[2] + S

if flip == 0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

flip = 0
for _ in range(Q):
    q = input().split()
    if q[0] == "1":
        flip += 1
        flip %= 2
    else:
        if (int(q[1]) - 1 + flip)%2 == 0:
            S.appendleft(q[2])
        else:
            S.append(q[2])

S = list(S)
if flip == 0:
    print(*S, sep="")
else:
    print(*S[::-1], sep="")
### BUGGY CODE ###

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

def find(target, list):
    for i in range(len(list)):
        if list[i] == target:
            return i+1

out = []
for j in range(1, n+1):
    out.append(find(j, a))

print(" ".join(map(str, out)))


### FIXED CODE ###

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

out = sorted(range(1, len(a)+1 ), key=lambda i: a[i-1])
print(" ".join(map(str, out)))
### BUGGY CODE ###

def main():
    # initialize
    _ = int(input())
    nums = [int(n) for n in input().split(' ')]

    hash_table = {}
    for n in nums:
        if n in hash_table.keys():
            hash_table[n] += 1
        else:
            hash_table[n] = 1

    ans_cash = {}
    for n in nums:
        if n in ans_cash.keys():
            ans = ans_cash[n]
        else:
            ans = 0
            for k, v in hash_table.items():
                if k == n:
                    v -= 1
                ans += v * (v - 1) / 2 if v > 1 else 0
            ans_cash[n] = ans
        print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    # initialize
    _ = int(input())
    nums = [int(n) for n in input().split(' ')]

    hash_table = {}
    for n in nums:
        if n in hash_table.keys():
            hash_table[n] += 1
        else:
            hash_table[n] = 1

    ans_cash = {}
    for n in nums:
        num_n = hash_table[n]
        if num_n in ans_cash.keys():
            ans = ans_cash[num_n]
        else:
            ans = 0
            for k, v in hash_table.items():
                if k == n:
                    v -= 1
                ans += v * (v - 1) / 2 if v > 1 else 0
            ans_cash[num_n] = ans
        print(int(ans))


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

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


l = [(x+1)/2 for x in range(1,1001)]

ansSum = 0
for i in range(n-k+1):
    List = p[i:i+k]
    Sum = sum(List)
    if Sum > ansSum:
        ansSum = Sum
        ansList = List

ans = 0
for j in ansList:
    ans += l[j-1]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = 0
for i in range(n-k+1):
    ans = max(ans, s[i+k] - s[i])
print(ans)
### BUGGY CODE ###

n,s=open(0);a=i=j=0
while j<1e7:f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

### FIXED CODE ###

from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include<iostream>
using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')
### BUGGY CODE ###

import sys
from collections import Counter

n=int(input())
a=[0]+[list(map(int,sys.stdin.readline().strip().split()[::-1])) for _ in range(n)]

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    x=[]

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        x.append((min(i,a[i][-1]),max(i,a[i][-1])))
    
    cnt=Counter(x)

    for (i,j),v in cnt.most_common():
        if v==1:
            break

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)

def dfs(v, pv):
    global P

    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)

n,q = map(int, input().split())
G = [[] for _ in range(n)]              # adjacent list
for i in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


dfs(0, 0)
print(*P)



### FIXED CODE ###

import sys
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数求めたい
from math import ceil, floor, sqrt #小数点切り上げ、切り捨て、平方根求めたい
from copy import deepcopy #参照で影響されないコピーが作られる
from collections import Counter, deque #要素ごとの出現回数を数える。双方向アクセス可能データ型
import heapq
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template


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

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

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

for i in range(q):
    p,x = map(int, input().split())
    o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
    p = todo.pop(-1)
    ct[p] += o[p]
    seen[p] = True
    for i in g[p]:
        if seen[i]:
            ct[p] += ct[i]
        else:
            todo.append(i)

print(*ct[1:])