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

def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = -m
        temp[1] = (s.count("(")-s.count(")"))-m
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()


### FIXED CODE ###

def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = -m
        temp[1] = (s.count("(")-s.count(")"))-m
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys
import random


def is_prime3(q, k=50):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l,r+1,2):
        if is_prime3(i) and is_prime3((i+1)//2):
            ans+=1
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += pow(2, i, pc + 1)
        m01 %= pc + 1
        m10 += pow(2, i, pc - 1)
        m10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


@lru_cache(maxsize=None)
def F(n):
    if n == 0:
        return 0
    return F(n % pop_count(n)) + 1


ans = [0] * N
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += 1 << i
        m %= pc + 1
    else:
        m = m10
        m -= 1 << i
        m %= pc - 1
    ans[i] = F(m) + 1

print(*ans[::-1], sep="\n")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += b01
        m01 %= pc + 1
        m10 += b10
        m10 %= pc - 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += b01
        m %= pc + 1
    else:
        m = m10
        m -= b10
        m %= pc - 1
    ans[i] = memo[m] + 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        bB = N - r*R - g*G
        if bB%B == 0 and 0<=(bB//B):
            ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())

ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        bB = N - r*R - g*G
        if bB%B == 0 and 0<=(bB//B):
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
pdt = 1
for i in range(n):
  pdt *= a[i]
if pdt>10**18:
  print(-1)
else:
  print(pdt)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
pdt = 1
a.sort()
for i in range(n):
  pdt *= a[i]
  if pdt==0:
    print(pdt)
    break
  elif pdt>10**18:
    print(-1)
    break
else:
  print(pdt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
def seek(LIST:list):
    global ans
    max_num = max(LIST)
    index = LIST.index(max(LIST))
    if(index == 0):
        ans += max_num*len(LIST)-sum(LIST)
    else:
        cal_LIST = LIST[index:]
        ans += max_num*len(cal_LIST)-sum(cal_LIST)
        new_list = LIST[0:index]
        seek(new_list)
seek(A)
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
max_num = A[0]
ans = 0
for i in A:
    if(max_num>=i):
        ans += max_num-i
    else:
        max_num = i
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Dec 20 12:35:48 2017

"""
 
from collections import Counter

NKList = list(map(int,input().split()))
N = NKList[0]
K = NKList[1]

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

countDict = Counter(AList)
soretedList = sorted(countDict.values())

rewrite = 0

while len(soretedList) > K:
    head = soretedList.pop(0)
    rewrite += head
    
print(rewrite)

    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Dec 20 12:35:48 2017

"""
 
from collections import Counter

NKList = list(map(int,input().split()))
N = NKList[0]
K = NKList[1]

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

countDict = Counter(AList)
soretedList = sorted(countDict.values())

l = len(soretedList)

if len(soretedList) <= K :
    print(0)
else:
    print(N - sum(soretedList[l-K:] ))
### BUGGY CODE ###

import math

# H, N = 9, 3
# ARR = [
#     [8, 3],
#     [4, 2],
#     [2, 1]
# ]
#
#
# H, N = 100, 6
# ARR = [
#     [1, 1],
#     [2, 3],
#     [3, 9],
#     [4, 27],
#     [5, 81],
#     [6, 243]
# ]
#

H,N = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))


def calculate(h, n, arr):
    brr = []
    for i in range(h + 1):
        brr.append(math.inf)

    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):

            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[i]+cost, brr[nextDamage])

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)


### FIXED CODE ###

import math

# H, N = 9, 3
# ARR = [
#     [8, 3],
#     [4, 2],
#     [2, 1]
# ]
#
#
# H, N = 100, 6
# ARR = [
#     [1, 1],
#     [2, 3],
#     [3, 9],
#     [4, 27],
#     [5, 81],
#     [6, 243]
# ]
#

H, N = map(int, input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int, input().split())))


def calculate(h, n, arr):
    brr = [math.inf] * (h+1)
    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):

            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[i] + cost, brr[nextDamage])

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)
### BUGGY CODE ###

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

seta = set(a)
ans = 0
if 1 not in seta:
  print(-1)
  sys.exit()
for i in range(1,n+1):
  if i in seta:
    idx = a.index(i)
  else:
    ans += len(a) 
    break 
  ans += idx
  a = a[idx+1:]
  seta = set(a)
  
print(ans)


### FIXED CODE ###

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

ans = 0
if 1 not in a:
  print(-1)
  sys.exit()
  
index = 1
for i in a:
  if i != index:
    ans+=1
  else:
    index+=1
    
print(ans)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

i = len(s)
j = len(t)
ans = []
while i and j:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

ans = "".join(ans[::-1])
print(ans)


### FIXED CODE ###

s = input()
t = input()


dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

i = len(s)
j = len(t)
ans = []
while i and j:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

ans = "".join(ans[::-1])
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
a = [-1] + list(map(int, input().split(" ")))
 
i = 1
head = []
used = []
roop = []
 
inte=False
for _ in range(k):
    i = a[i]
    if i in used:
        used.append(i)
        head = used[0: used.index(i)]
        roop = used[used.index(i): -1]
        inte =True
        break
    else:
        used.append(i)
 
if inte:
    if len(head) >= k:
        print(head[k-1])
    else:
        x = (k - 1 - len(head)) % len(roop)
        print(roop[x])
else:
    print(used[k-1])


### FIXED CODE ###

import sys

n, k = map(int, input().split(" "))
a = [-1] + list(map(int, input().split(" ")))

i = 1
head = []
used = {}
roop = []

index = 0
for _ in range(k):
    index += 1
    i = a[i]
    if i in used:
        head = [ k for k, v in sorted(used.items(), key=lambda x:x[1]) if v < used[i]]
        roop = [ k for k, v in sorted(used.items(), key=lambda x:x[1]) if v >= used[i]]
        if len(head) >= k:
            print(head[k-1])
        else:
            x = (k - 1 - len(head)) % len(roop)
            print(roop[x])
            sys.exit()
    else:
        used[i] = index

print([ k for k, v in sorted(used.items(), key=lambda x:x[1])][k-1])
### BUGGY CODE ###

from collections import deque


def main():

    h, w = map(int, input().split())
    a = ["#" * (w + 2)] + ["#" + input() + "#" for _ in range(h)] + ["#" * (w + 2)]

    d = [[-1] * (w + 2) for _ in range(h + 2)]

    def bfs():
        q = deque()
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if a[i][j] == "#":
                    q.append((j, i))
                    d[i][j] = 0

        dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

        ans = 0
        while q:
            ux, uy = q.popleft()
            for dx, dy in dxy:
                vx = ux + dx
                vy = uy + dy
                if d[vy][vx] == -1 and a[vy][vx] == ".":
                    d[vy][vx] = d[uy][ux] + 1
                    ans = max(ans, d[vy][vx])
                    q.append((vx, vy))

        return ans

    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from scipy.ndimage import distance_transform_cdt


def main():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


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

N,K=map(int,input().split())
p=list(map(int,input().split()))
p_=[i for i in range(N)]
for a in range(N):
    p_[a]=(1+p[a])/2
A=[]          
for i in range(N-K+1):
            A.append(sum(p_[i:i+K]))
print(max(A))


### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))

p_=[]
for i in range(len(p)):
  p_.append((1+p[i])/2)
 
import itertools
c=list(itertools.accumulate(p_))

ans=0
if N!=K:
  
  for i in range(0,N-K):
    s=c[i+K]-c[i]
    ans=max(ans,s)
else:
  ans=c[K-1]
print(ans)
### BUGGY CODE ###

arr = input().split()
a = int(arr[0])
b = int(arr[1])
c = int(arr[2])
k = int(arr[3])
sum = 0
while a > 0 and k > 0:
  sum += 1
  k -= 1
  a -= 1
  
while b > 0 and k > 0:
  k -= 1
  b -= 1
  
while c > 0 and k > 0:
  k -= 1
  sum -= 1
  c -= 1
  
print(sum)

### FIXED CODE ###

arr = input().split()
a = int(arr[0])
b = int(arr[1])
c = int(arr[2])
k = int(arr[3])

if k <= a: print(k)
  
elif k <= (a+b): print(a)
  
else: print(a - (k - a - b))
### BUGGY CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect.bisect_left(L[j+1:], L[i]+L[j])
print(answer)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)
### BUGGY CODE ###

from collections import deque

N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a].append(b)
    edges[b].append(a)

color_num = 0
for i in range(N):
    if len(edges[i]) > color_num:
        color_num = len(edges[i])


color_stack = deque([[]])
node_stack = deque([0])
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = edges[current]
    can_color = [i+1 for i in range(color_num)]
    for color in used_colors:
        can_color.remove(color)
    for node in nodes:
        if reached[node]:
            continue
        color = can_color.pop()
        node_stack.append(node)
        color_stack.append([color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])



### FIXED CODE ###

from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()

    used_colors = set([colors[p[0]] for p in mat[current] if colors[p[0]] > 0])
    col = 1

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        while col in used_colors:
            col += 1
        colors[p[0]] = col
        col += 1
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)
### BUGGY CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i in range(N)])
#A = list(set(A))
A = sorted(A)#わるほう

kouho = list(A.copy())#わられるほう
target = sorted(list(set(A)))

for i in range(1,len(kouho)):
    if (kouho[i-1]==kouho[i]):
        if kouho[i] in target:
            target.remove(kouho[i])
            
kouho = sorted(target.copy())

for i in range(len(A)):
    if target == []:
        break
    maxN = int(max(target)/A[i])
    for n in range(2,maxN+1):
        if A[i]*n in kouho:
            kouho.remove(A[i]*n)
            #print(A[i]*n)
    target = list(kouho.copy())
        
print(len(target))

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
### BUGGY CODE ###

import bisect

n, q = map(int, input().split())
s = input()
index = []
for i in range(n):
    if s[i:i + 2] == "AC":
        index.append(i)
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 2
    bl = bisect.bisect_left(index, l)
    br = bisect.bisect_left(index, r)
    if r in set(index):
        print(br - bl + 1)
    else:
        print(br - bl)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac = []
last = False
for i in range(n):
    if last and s[i] == "C":
        last = False
        ac.append(1)
    else:
        if s[i] == "A":
            last = True
        else:
            last = False
        ac.append(0)
ac_t = [0]
for i in range(n):
    ac_t.append(ac[i] + ac_t[i])
for i in range(q):
    l, r = map(int, input().split())
    print(ac_t[r] - ac_t[l])
### BUGGY CODE ###

import math
for n in range(1, int(input())+1):
    b=0
    a=[0]*103
    l=int(math.sqrt(n)) + 1
    for i in range(1, l + 1):
        if a[i]: continue
        for j in range(1, l + 1):
            if a[j]: continue
            # we know z at this point
            d = i + j
            c = n - i**2 - j**2 - i*j
            try:
                k = int(math.sqrt(d**2 + 4*c) - d - 1)
                if k < 1: continue
                if n == (i**2 + j**2 + k**2 + i*j + j*k + i*k):
                    a[i] = True
                    a[j] = True
                    a[k] = True
                    if i == j and i == k and j == k:
                        b+= 1
                    elif i != j and i != k and j !=k:
                        b+=6
                    else:
                        b+=3
            except:
                pass
    print(b)

### FIXED CODE ###

n = int(input())
a = [0]*(n+1)
for i in range(1, 102):
    for j in range(1, 102):
        for k in range(1, 102):
            if (i*i + j*j + k*k + i*j + j*k + i*k) <= n:
                a[i*i + j*j + k*k + i*j + j*k + i*k] +=1
for x in a[1:]:
    print(x)
### BUGGY CODE ###

N, K=map(int, input().split())
H=list(map(int, input().split()))
MAXV=10**9
dp=[MAXV for _ in range(N)]
dp[0]=0
for i in range(1, N):
  minv=MAXV
  dp[i]=min([dp[j]+abs(H[j]-H[i]) if j>=0 else MAXV for j in range(i-K, i)])
print(dp[-1])

### FIXED CODE ###

N, K=map(int, input().split())
H=list(map(int, input().split()))
MAXV=10**9
dp=[MAXV for _ in range(N)]
dp[0]=0
for i in range(1, N):
  minv=MAXV
  dp[i]=min([dp[j]+abs(H[j]-H[i]) if j>=0 else MAXV for j in range(i-K, i)])
print(dp[-1])
### BUGGY CODE ###

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


def DFS(num,point):
    D[num]=point+Q[num]
    color[num]="gray"
    for i in M[num]:
        if color[i]=="white":
            DFS(i,D[num])
    color[num]="black"


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

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

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

color=["white" for _ in range(n+1)]
D=[0]*(n+1)

DFS(1,0)
print(*D[1:])

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

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

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)