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

from collections import defaultdict, deque

class Node(object):

    def __init__(self, id, person_id=None, children_id=[]):
        self.id = id
        self.person_id = person_id
        self.children_id = children_id
        self.counter = 0


# 標準入力とadj_dictの構築
N, Q = map(int, input().split())

adj_dict = defaultdict(list)
for i in range(N-1):
    ai, bi = map(int, input().split())
    adj_dict[ai].append(bi)
    adj_dict[bi].append(ai)


# グラフの構築
cur_id = 1
cur_node = Node(id=cur_id,
                person_id=None,
                children_id=[])
node_dict = {cur_id:cur_node}
open_list = deque()
open_list.append(cur_id)
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    cur_node = node_dict[cur_id]
    adj_list = adj_dict[cur_id]
    for adj_id in adj_list:
        if adj_id != cur_node.person_id:
            cur_node.children_id.append(adj_id)
            open_list.append(adj_id)
            adj_node = Node(id=adj_id,
                            person_id=cur_id,
                            children_id=[])
            node_dict[adj_id] = adj_node

# 操作jを1つのnodeに対してのみ行う
cur_node = node_dict[1]
p, x = [], []
for i in range(Q):
    pi, xi = map(int, input().split())
    node = node_dict[pi]
    node.counter += xi

# 親ノードから天下り的に加算していく
cur_id = 1
open_list = deque()
open_list.append(cur_id)
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    cur_node = node_dict[cur_id]
    if cur_node.person_id != None:
        cur_node.counter += node_dict[cur_node.person_id].counter
    for child_id in cur_node.children_id:
        open_list.append(child_id)

# 出力
res = []
for id in range(1, N+1):
    res.append(node_dict[id].counter)

print(*res)

### FIXED CODE ###

from collections import defaultdict

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

cnt = [0]*(N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

root_node = (1, -1) # (id, value, parent_id)
open_list = [root_node]
closed_list = []
while True:
    if len(open_list) == 0:
        break
    cur_node = open_list.pop()
    cur_id, parent_id = cur_node
    if not(parent_id == -1):
        cnt[cur_id] += cnt[parent_id]
    for child_id in edge[cur_id]:
        if child_id == parent_id:
            continue
        open_list.append((child_id, cur_id))
print(*cnt[1:])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    for j in range(i+2, n):
        if a[i] >= abs(i-j) or a[j] >= abs(i-j):
          if a[i] > abs(i-(n-1)): break
          else: continue 
        if abs(i-j) == a[i]+a[j]: ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
c = {}

ans = 0
for i in range(n):
    b.append(a[i]+i+1)
    x = -a[i]+i+1
    if x in c:
        c[x] += 1
    else:
        c[x] = 1
for i in range(n):
    if b[i] in c:
        ans += c[b[i]]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			for i in range(-2, 2+1):
				for j in range(-2, 2+1):
					if (i, j) == (0, 0):
						continue
					if getMaze(x + i, y + j) == ".":
						if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
							graph[y][x].append((x + i, y + j, 0))
						else:
							graph[y][x].append((x + i, y + j, 1))


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[float("inf")]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		log.print(x, y, dist[y][x])
		if dist[y][x] == float("inf"):
			dist[y][x] = 0
		d = dist[y][x]
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] > d + cost:
				dist[ny][nx] = d + cost
				if cost == 1:
					stack.append((nx, ny))
				else:
					stack.appendleft((nx, ny))
	log.print(dist)
	if dist[dh-1][dw-1] == float("inf"):
		print(-1)
	else:
		print(dist[dh-1][dw-1])
	
	


main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[float("inf")]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		log.print(x, y, dist[y][x])
		if dist[y][x] == float("inf"):
			dist[y][x] = 0
		d = dist[y][x]
		nexts = []
		for i in range(-2, 2+1):
			for j in range(-2, 2+1):
				if (i, j) == (0, 0):
					continue
				if getMaze(x + i, y + j) == ".":
					if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
						nexts.append((x + i, y + j, 0))
					else:
						nexts.append((x + i, y + j, 1))
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] > d + cost:
				dist[ny][nx] = d + cost
				if cost == 1:
					stack.append((nx, ny))
				else:
					stack.appendleft((nx, ny))
	log.print(dist)
	if dist[dh-1][dw-1] == float("inf"):
		print(-1)
	else:
		print(dist[dh-1][dw-1])
	
	


main()
### BUGGY CODE ###

import numpy as np
N = int(input())  # 個数
A = np.array([int(i) for i in input().split()], dtype=np.int64)  # 整数

sum_a = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum_a += (A[i] * A[j]) % 1000000007

print(sum_a % 1000000007)

### FIXED CODE ###

N = int(input())  # 個数
A = [int(i) for i in input().split()]  # 整数

sum_Aij = 0
sum_j = [0] * (N - 1)
for i in range(N - 1, 0, -1):
    sum_j[i - 1] = (A[i] + (0 if i == N - 1 else sum_j[i])) % 1000000007
    sum_Aij += sum_j[i - 1] * A[i - 1] % 1000000007

print(sum_Aij % 1000000007)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
l,r=[],[]
for i in range(Q):
    l0,r0=map(int,input().split())
    l.append(l0)
    r.append(r0)
c=[]
for i in range(N):
    c.append(0)
for i in range(N-1):
    if (S[i]=='A') and (S[i+1]=='C'):
        c[i]+=1
for i in range(Q):
    print(sum(c[l[i]-1:r[i]-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(N-1):
    t[i+1]=t[i]+(1 if S[i:i+2]=='AC' else 0)
for i in range(Q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

n, k, q = map(int,input().split())
A = [int(input()) for i in range(q)]
B = [k] * n

for i in A:
    B[i-1] = B[i-1] + 1
    for j in range(n):
        B[j] = B[j] - 1


for k in range(n):
    if B[k] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int,input().split())
A = [int(input()) for i in range(q)]
B = [k] * n

for i in A:
    B[i-1] = B[i-1] + 1



for k in range(n):
    if B[k]-q > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford
N, M = [int(i) for i in input().split()]
rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-1)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
for i in range(N):
    try:
        d1 = bellman_ford(graph, indices = [i], directed=True, unweighted=False)
    except:
        print(0)
        exit()
else:
    print(-1)


### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]


for i in range(M):
    u, v = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, 1)
    g.add_edge(u-1+N, v-1, 1)
    g.add_edge(u-1, v-1+N, 1)

d = Dijkstra(g, 0)

ans_n = 10 ** 6
ans_index = -1
for i in range(N):
    d = Dijkstra(g, i)
    ans_n_ = d.dist[i+N]

    if ans_n_ < ans_n:
        ans_index = i
        ans_n = ans_n_

if ans_n == 10 ** 6:
    print(-1)
else:
    d = Dijkstra(g, ans_index)
    ans = d.shortest_path(ans_index + N)
    ans.sort()
    print(ans_n)
    for j in range(ans_n):
        print(ans[j]+1)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        d = j - i
        for k in range(j+1, N):
            if d == k - j:
                continue
            if S[i] == S[k] or S[j] == S[k]:
                continue
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
r, g, b = 0, 0, 0
for c in S:
    if c == "R":
        r += 1
    elif c == "G":
        g += 1
    else:
        b += 1
ans = r * g * b
sub = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            continue
        k = 2 * j - i
        if k >= N or S[k] == S[i] or S[k] == S[j]:
            continue
        sub += 1
print(ans - sub)
### BUGGY CODE ###

A, B = [int(_) for _ in input().split()]
res = A
for i in range(A + 1, B + 1):
    res = res ^ i
print(res)

### FIXED CODE ###

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

def xor(n):
  if n % 2 == 0:
    return (((n + 1) // 2) % 2) ^ n
  else:
    return ((n + 1) // 2) % 2
print(xor(A-1) ^ xor(B))
### BUGGY CODE ###

n, m, q = list(map(int, input().split()))
lst = [[0]*n for i in range(n)]
for i in range(m):
    l, r = list(map(int, input().split()))
    lst[l-1][r-1] += 1
pq = list(list(map(int, input().split())) for i in range(q))
for a, b in pq:
    ans = sum([sum(lst[i][a-1:b]) for i in range(a-1, b)])
    print(ans)

### FIXED CODE ###

from numpy import cumsum 
n, m, q = list(map(int, input().split()))
lst = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l, r = list(map(int, input().split()))
    lst[l][r] += 1
ans1 = cumsum(lst, axis=1)
ans = cumsum(ans1, axis=0)
for i in range(q):
    a, b = list(map(int, input().split()))
    print(ans[b, b] - ans[a-1, b])
### BUGGY CODE ###

n,k = map(int, input().split())
d={}
l = list(map(int, input().split()))
for i in range(len(l)):
    d[i+1] = l[i]

city = 1
l2 = [1]
while True:
    city = d[city]
    if city in l2:
        break
    l2.append(city)

first = l2.index(city)
if len(l2) <= k:
    if city == l2[-1]:
        print(city)
    else:
        l2 = l2[first:]
        print(l2[(k-first)%(len(l2))])
else:
    print(l2[k])

### FIXED CODE ###

n,k = map(int, input().split())
l = [0]+list(map(int, input().split()))

journey = [1]

for i in range(2*n):
    next = l[journey[-1]]
    journey.append(next)
if k <= n+1:
    print(journey[k])
    exit()

end = n
start = n-1

while journey[start] != journey[end]:
    start -= 1

period = end - start
k %= period

while k < n:
    k += period

print(journey[k])
### BUGGY CODE ###

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

sa = 0
sb = 0
for i in range(n):
    if i % 2 == 0:
        ab.sort(reverse=True)
        sa += ab[0][0]
        ab.pop(0)
    else:
        ab = sorted(ab, key=lambda x: x[1], reverse=True)
        sb += ab[0][1]
        ab.pop(0)
        
print(sa-sb)

### FIXED CODE ###

n = int(input())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a+b,a,b])
    
ab.sort(reverse=True)
suma = 0
sumb = 0
for i in range(n):
    if i % 2 == 0:
        suma += ab[i][1]
    else:
        sumb += ab[i][2]
print(suma-sumb)
### BUGGY CODE ###

from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

n,k = tuple(map(int,input().split())) 
N = list(map(int,input().split()))
m = 0
for i in range(0,n-k+1):
    if m < sum(N[i:i+k]):
        m = sum(N[i:i+k])
print((m+k)/2)

### FIXED CODE ###

n,k = tuple(map(int,input().split())) 
N = list(map(int,input().split()))
s = sum(N[0:k])
m = sum(N[0:k])

for i in range(0,n-k):
    s = s-N[i]+N[i+k]
    m = max(m,s)   
print((m+k)/2)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
from itertools import accumulate
import numpy as np

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

sum_A = list(accumulate(A))
sum_B = list(accumulate(B))

#sum_A = np.cumsum(A)
#sum_B = np.cumsum(B)

list_N = [0 for i in range(len(A)+1)]

pre_n = len(B)

for i in range(len(A)+1):
    if i == 0:
        buf = np.array(sum_B[:pre_n])
        num_B = len(buf[buf<=K])
        pre_n = num_B
        list_N[i] = i + num_B
    else:
        if K>=sum_A[i-1]:
            buf = np.array(sum_B[:pre_n])
            num_B = len(buf[buf<=(K-sum_A[i-1])])
            pre_n = num_B
            list_N[i] = i + num_B
        else:
            list_N[i] = 0
    
print(np.max(list_N))

### FIXED CODE ###

# coding: utf-8
# Your code here!
from itertools import accumulate
#import numpy as np

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

sum_A = list(accumulate(A))
sum_B = list(accumulate(B))


#sum_A = np.cumsum(A)
#sum_B = np.cumsum(B)

list_N = [0 for i in range(len(A)+1)]

pre_n = len(B)

for i in range(len(A)+1):
    if i == 0:
        num_B = 0
        for j in range(pre_n)[::-1]:
            if sum_B[j] <= K:
                num_B = j+1
                break
            else:
                continue
        #len(buf[buf<=K])
        pre_n = num_B
        list_N[i] = i + num_B
    else:
        if K>=sum_A[i-1]:
            num_B = 0
            for j in range(pre_n)[::-1]:
                if sum_B[j] <= (K-sum_A[i-1]):
                    num_B = j+1
                    break
                else:
                    continue
            #len(buf[buf<=(K-sum_A[i-1])])
            pre_n = num_B
            list_N[i] = i + num_B
            #print(K-sum_A[i-1])
            #print(i, num_B)
        else:
            list_N[i] = 0
    
#print(A)
#print(B)
#print(sum_A)
#print(sum_B)
#print(list_N)
print(max(list_N))
### BUGGY CODE ###

#C
N,K = map(int,input().split())
old = N
while True:
    new = abs(K-old)
    if old < new:
        break
    else:
        old = new
print(old)



### FIXED CODE ###

#C
N,K = map(int,input().split())
r = N%K
if N <= K:
    print(min(K-N,N))
else:
    print(min(r,K-r))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(numbers, queries, H, W, D):
    dp = [[-1] * (H*W+1) for _ in range(H*W+1)]

    for l, r in queries:
        ans = 0
        while True:
            if l == r:
                break
            if dp[l][l+D] == -1:
                dp[l][l+D] = sub_solve(l, l+D)
            res = dp[l][l+D]
            ans += res
            l += D
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, H, W, D)


if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(queries, H, W, D):
    dp = [0] * (H*W+1)
    for i in range(D+1, H*W+1):
        dp[i] = dp[i-D] + sub_solve(i-D, i)

    for l, r in queries:
        ans = dp[r] - dp[l]
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())

    for y in range(1, H+1):
        tmp = [int(x) for x in input().split()]
        for x, i in enumerate(tmp, start=1):
            numbers[i] = (x, y)

    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    solve(queries, H, W, D)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
DP = [[0 for _ in range(N)] for _ in range(K+1)]
for i in range(N):
    DP[0][i] = A[i]

for i in range(1, K+1,1):
    for j in range(N):
        pl, mi = min(j + DP[i-1][j], N-1), max(j - DP[i-1][j], 0)
        for k in range(mi, pl+1, 1):
            DP[i][k] += 1

print(" ".join(map(str, DP[K])))

### FIXED CODE ###

import sys
N, K = map(int, input().split())
if K > 42:
    print(" ".join(map(str, [N] * N)))
    sys.exit()
A = [int(i) for i in input().split()]
DP = [[0 for _ in range(N)] for _ in range(K+1)]
for i in range(N):
    DP[0][i] = A[i]

for i in range(1, K+1,1):
    B = [0] * N
    for j in range(N):
        pl, mi = min(j + DP[i-1][j], N-1), max(j - DP[i-1][j], 0)
        B[mi] += 1
        if pl + 1 < N:
            B[pl + 1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    DP[i] = B
print(" ".join(map(str, DP[K])))
### BUGGY CODE ###

from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    # parents = deque()
    # parents.append(0)
    parents = set()
    parents.add(0)
    visited = set()
    while parents:
        # parent = parents.popleft()
        parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        if parent in edges:
            for child in edges[parent]:
                if child in visited:
                    continue
                # if counter[child] != 0:
                #    continue
                counter[child] = counter[parent]
                # print("child")
                # print(child, counter[child])
                # parents.append(child)
                parents.add(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    p = defaultdict(int)
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)