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

def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    ans = TLE(S)

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


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

N = int(input())
a = [int(x) for x in input().split()]

p = [0] * 3
for i in a:
    p[3-i] += 1

dp = [[[0] * (N+1-i-j) for j in range(N+1-i)] for i in range(N+1)]

for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            if i + j + k == 0:
                continue
            if i > 0:
                dp[i][j][k] += dp[i-1][j+1][k] * i
            if j > 0:
                dp[i][j][k] += dp[i][j-1][k+1] * j
            if k > 0:
                dp[i][j][k] += dp[i][j][k-1] * k
            dp[i][j][k] += N
            dp[i][j][k] /= (i + j + k)

print(dp[p[0]][p[1]][p[2]])

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]

p = [0] * 3
for i in a:
    p[3-i] += 1

dp = [[[0] * (N+1-i-j) for j in range(N+1-i)] for i in range(N+1)]

for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            if i + j + k == 0:
                continue
            if i > 0:
                dp[i][j][k] += dp[i-1][j+1][k] * i
            if j > 0:
                dp[i][j][k] += dp[i][j-1][k+1] * j
            if k > 0:
                dp[i][j][k] += dp[i][j][k-1] * k
            dp[i][j][k] += N
            dp[i][j][k] /= (i + j + k)

print(dp[p[0]][p[1]][p[2]])
### BUGGY CODE ###

#intの場合
N = int(input()) #ここで標準入力

#List にしたい時
#intの場合
huga = list(map(int, input().split()))
ans = 1
for number in huga:
    ans = ans * number
    

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

#intの場合
N = int(input()) #ここで標準入力

#List にしたい時
#intの場合
huga = list(map(int, input().split()))
if 0 in huga:
    print(0)
else:
    ans = 1
    flg = 0
    for number in huga:
        ans = ans * number
        if ans > 10**18:
            flg = 1
            break
    if flg == 0:
        print(ans)
    else:
        print('-1')
### BUGGY CODE ###

n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ma=max(A)
ng=(ma**2)*m+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+2

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)
### BUGGY CODE ###

k = int(input())
ans = 1
num = 0
if not k%2:
    print(-1)
else:
    while True:
        num = (num*10+7)%k
        if num == 0:
            print(ans)
            break
        ans += 1

### FIXED CODE ###

k = int(input())
num = 0
if not k%2:
    print(-1)
else:
    for i in range(k):
        num = (num*10+7)%k
        if num == 0:
            print(i+1)
            break
    else:
        print(-1)
### BUGGY CODE ###

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

while abs(n-k) <= n:
    n = abs(n-k)

print(n)


### FIXED CODE ###

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

t = n % k

if t < (k - t):
    print(t)
else:
    print(k - t)
### BUGGY CODE ###

k, s = [int(i) for i in input().split()]

count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = [int(i) for i in input().split()]

count = 0
for x in range(k,-1,-1):
    a = s - x
    if a > 2*k:
        break
    elif a == 0:
        count += 1
        continue

    if a >= k:
        tmp = k
    else:
        tmp = a

    for y in range(tmp, -1, -1):
        z = a - y
        if z > k :
            break
        else:
            count += 1

print(count)
### BUGGY CODE ###

from collections import Counter
n = int(input())
d_li = list(map(int,input().split()))
m = int(input())
t_li = list(map(int,input().split()))

t_counter = Counter(t_li)
t_li = t_counter.most_common()
t_len = len(t_li)
for i in range(t_len):
    dum = t_li[i][0]
    if d_li.count(dum) >= t_li[i][1]:
        pass
    else:
        print("NO")
        exit()
print("YES")

### FIXED CODE ###

from collections import Counter
n = int(input())
d_li = list(map(int,input().split()))
m = int(input())
t_li = list(map(int,input().split()))

d_counter = Counter(d_li)
t_counter = Counter(t_li)
t_most_counter = t_counter.most_common()
t_len = len(t_most_counter)
for i in range(t_len):
    dum = t_most_counter[i][0]
    if d_counter[dum] >= t_most_counter[i][1]:
        pass
    else:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

from itertools import combinations
n,k=map(int,input().split())
*A,=sorted(map(int,input().split()))
mod=10**9+7
 
mi,ma=0,0
for i in list(combinations(A,k)):
    mi+=i[0]
    ma+=i[-1]
print((ma-mi)%mod)

### FIXED CODE ###

M,K = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
ANS = 0
 
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
for j in range(M-K+1):
    ANS += (L[K-1+j] - L[M-K-j])*cmb(K-1+j,K-1,mod)
 
print(ANS % mod)
### BUGGY CODE ###

def main():
    import sys
    from collections import deque

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

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        while any(il):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###


n,a,b = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
INF = 500
dp = [[[INF for i in range(411)] for j in range(411)] for k in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(a*n+1):
        for k in range(b*n+1):
            if j - l[i][0]>=0 and k - l[i][1]>=0:
                dp[i+1][j][k] = min(dp[i][j][k],dp[i][j - l[i][0]][k - l[i][1]]+l[i][2])
            else:
                dp[i+1][j][k] = dp[i][j][k]
i =1
ans = INF
while i*max(a,b)<=400:
    ans = min(ans, dp[n][i*a][i*b])
    i+=1
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###


n,a,b = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
INF = 500
dp = [[[INF for i in range(411)] for j in range(411)] for k in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(a*n+1):
        for k in range(b*n+1):
            if j - l[i][0]>=0 and k - l[i][1]>=0:
                dp[i+1][j][k] = min(dp[i][j][k],dp[i][j - l[i][0]][k - l[i][1]]+l[i][2])
            else:
                dp[i+1][j][k] = dp[i][j][k]
i =1
ans = INF
while i*max(a,b)<=400:
    ans = min(ans, dp[n][i*a][i*b])
    i+=1
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    friend = {e: set() for e in range(n)}
    foe = {e: set() for e in range(n)}
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        foe[c].add(d)
        foe[d].add(c)

    for i in range(n):
        print(len(set(members(i)) - friend[i] - foe[i]) - 1, end=' ')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

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

N,M = (int(x) for x in input().split())
A = sorted([int(x) for x in input().split()])

for i in range(M):
    B,C = map(int,input().split())
    
    if A[-1] <= C:  j,m = B,N
    elif A[0] >= C: j,m = 0,0
    else:
        m,s,e = N//2, 0, N
        while A[m] > C or C > A[m+1]:
            if A[m] > C:    e = m
            elif C > A[m+1]:    s = m+1
            m = (s+e)//2
        
        if B < m:   j = B
        else:   j = m 

    A = A[j:m+1] + [C]*j + A[m+1:N]
print(sum(A))
    

### FIXED CODE ###

import numpy as np

N,M = map(int,input().split())
A = sorted([int(x) for x in input().split()])
An = 0
C = []

for i in range(M):
    C += [[int(x) for x in input().split()]]
    
C = sorted(C,key=lambda x: x[1])[::-1]

m = 0
for i in range(M):
    b = C[i][0]
    if m == N:
        break
    if m+b >= N:
        b = N-m

    if A[m + b - 1] < C[i][1]:
        m = m + b
        An += C[i][1]*b
    else:
        c = C[i][1]
        for j in range(2,b):
            if A[m+b-j] < c:
                m = m + b - j + 1
                An += c*(b-j+1)
                break
        break

if m == N:  print(An)
else:   print(sum(A[m:]) + An)
### BUGGY CODE ###

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

bits = 1 << N

xmemo = [[float('inf')]*N for _ in range(bits)]
ymemo = [[float('inf')]*N for _ in range(bits)]

for b in range(bits):
  for i in range(N):
    xmemo[b][i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b][i])
    ymemo[b][i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b][i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b][j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b][j])
      ymemo[b][j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b][j])
      
ans = [float('inf')]*(N+1)

for b in range(bits):
  b_ = b
  cnt = bin(b_).count('1')
  while b_ >= 0:
    b_ &= b
    yi = b - b_
    tmp = 0
    for i in range(N):
      tmp += min(xmemo[b_][i], ymemo[yi][i])
    ans[cnt] = min(ans[cnt], tmp)
    b_ -= 1
  
for i in range(N+1):
  print(ans[i])

### FIXED CODE ###

import sys

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

bits = 1 << N

xmemo = [sys.maxsize]*(N*bits)
ymemo = [sys.maxsize]*(N*bits)

for b in range(bits):
  for i in range(N):
    xmemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b*N+i])
    ymemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b*N+i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b*N+j])
      ymemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b*N+j])
      
ans = [sys.maxsize]*(N+1)

for b in range(bits):
  b_ = b
  cnt = bin(b_).count('1')
  while b_ >= 0:
    b_ &= b
    yi = b - b_
    tmp = 0
    for i in range(N):
      tmp += min(xmemo[b_*N+i], ymemo[yi*N+i])
    ans[cnt] = min(ans[cnt], tmp)
    b_ -= 1
  
for i in range(N+1):
  print(ans[i])
### BUGGY CODE ###

n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = min(cost[i],dp[int(key[i],0)])
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            k = int(key[j], 0)
            tar = k | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])





### FIXED CODE ###

n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = min(cost[i],dp[int(key[i],0)])
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            k = int(key[j], 0)
            tar = k | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

n=int(input())
info=[]
for i in range(n):
  info.append(list(input()))
  
for i in range(n):
  info[i].sort()
  
ans=0
for i in range(n):
  for j in range(n-i-1):
    if info[i]==info[i+j+1]:
      ans+=1
      
print(ans)

### FIXED CODE ###

import sys
#input = sys.stdin.readline

n = int(input())
note = dict()
ans = 0
for i in range(n):
    s = "".join(sorted(sys.stdin.readline()))
    if s in note.keys():
        ans += note[s]
        note[s] += 1
    else:
        note[s] = 1

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

k, s = map(int, input().split())
ks = [_ for _ in range(k+1)]

count = 0

for ksk1 in ks:
    for ksk2 in ks:
        if s -(ksk1 + ksk2) in ks:
            count += 1
            
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
ks = [_ for _ in range(k+1)]

count = 0

for ksk1 in ks:
    for ksk2 in ks:
        z = s - ksk1 - ksk2
        if 0 <= z <= k:
            count += 1
            
print(count)
### BUGGY CODE ###

N=int(input())
a=input().split()
count =0
ans=0
while(count%N==0):
 for i in range(N):
  a[i]=int(a[i])
  if(a[i]%2==0):
    a[i]=int(a[i]/2)
    count +=1
    ans=count   
ans=int(ans/N)
print(ans)
    

### FIXED CODE ###

N = int(input())
A = input().split()
judge = 1 #1:継続, 0:終了
count = 0

while(judge):
  for i in range(N):
   A[i] = int(A[i])
   if(A[i]%2 == 1):
    judge = 0
    break
   else:
    A[i] = A[i]/2
    count += 1

print(int(count/N))
### BUGGY CODE ###

N, M = map(int, input().split())
INF = 10**9
A = [INF for i in range(N)]
B = [INF for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  A[i] = a
  B[i] = b

ans = 0
count = 0
while(count < M):
  min_A = min(A)
  min_Ai = A.index(min_A)
  if count + B[min_Ai] > M:
    ans += min_A * (M - count)
    count = M
  else:
    ans += min_A * B[min_Ai]
    count += B[min_Ai]
  del A[min_Ai]
  del B[min_Ai]

print(ans)


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1
### BUGGY CODE ###

from queue import Queue
import sys
sys.setrecursionlimit(200005)

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

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

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

queue = Queue()
queue.put([0,1])
while not queue.empty():
    parent, node = queue.get()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.put([node, leaf])

for counter_i in counter[1:]:
    print(counter_i, end=" ")


### FIXED CODE ###

from collections import deque

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

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

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

queue = deque([[0,1]])
while queue:
    parent, node = queue.popleft()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.append([node, leaf])

print(*counter[1:])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

option = {(0, 0)}


def main():
    global option
    last_list = [0, 0, 0]
    N = int(input())
    for i in range(N):
        this_list = list(map(int, input().split()))
        add_option(this_list[0] - last_list[0])
        if (this_list[1], this_list[2]) not in option:
            print('No')
            return
        option = {(this_list[1], this_list[2])}
        last_list = this_list
    print('Yes')


def add_option(step):
    global option
    for i in range(step):
        temp_option = set()
        for position in option:
            x, y = position
            if x < 100000:
                temp_option.add((x + 1, y))
            if y < 100000:
                temp_option.add((x, y + 1))
            if x > 0:
                temp_option.add((x - 1, y))
            if y > 0:
                temp_option.add((x, y - 1))
        option = temp_option


main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

judge = 'Yes'

N = int(input())
for i in range(N):
    t, x, y = map(int, input().split())
    if t < (x + y) or t % 2 != (x + y) % 2:
        judge = 'No'

print(judge)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
M = max(A)

for i in range(N):
    if M == A[i]:
        A[i] *= -1
        print(max(A))
        A[i] *= -1
    else:
        print(M)

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

S = sorted(A)
M1 = S[-1]
M2 = S[-2]

for i in range(N):
    if A[i] == M1:
        print(M2)
    else:
        print(M1)
### BUGGY CODE ###

# LongestCommonSubsequences
S = input()
T = input()
Ns = len(S)
Nt = len(T)

dp = [[0] * (Nt + 1) for _ in range(Ns + 1)]

for i in range(Ns):
    for j in range(Nt):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i = Ns
j = Nt
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

ans = ans[::-1]
print(ans)


### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])