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

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

ans = 1
LIM = 10 ** 18
for a in A:
    ans *= a

if ans > LIM:
    ans = -1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

LIM = 10 ** 18

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    quit()

ans = 1
for a in A:
    ans *= a
    if ans > LIM:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
if n>=m:
  print(0)
else:
  l.sort()
  k=[]
  for i in range(m-1):
    x=l[i+1]-l[i]
    k.append(x)
    k.sort()
  sum=0
  for i in range(m-n):
    sum+=k[i]
  print(sum)

### FIXED CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
if n>=m:
  print(0)
else:
  l.sort()
  k=[]
  for i in range(m-1):
    x=l[i+1]-l[i]
    k.append(x)
  k.sort()
  sum=0
  for i in range(m-n):
    sum+=k[i]
  print(sum)
### BUGGY CODE ###

#!/usr/bin/env pypy3

import sys
import pprint
from collections import deque

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


def main():
	log = Logger(1)
	n = int(sys.stdin.readline())
	cnt = 0
	stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
	already = deque([])
	while len(stack) != 0:
		now = stack.popleft()
		already.append(now)
		cnt += 1
		if cnt == n:
			print(now)
			exit()
		if now % 10 == 0:
			nexts = [now * 10 + now % 10, now * 10 + now  % 10+ 1]
		elif now % 10 == 9:
			nexts = [now * 10 + now % 10 - 1, now * 10 + now % 10]
		else:
			nexts = [now * 10  + now % 10 - 1, now * 10 + now % 10, now * 10 + now % 10 + 1]
		for next in nexts:
			if next in already or next in stack:
				continue
			stack.append(next)


main()

### FIXED CODE ###

K = int(input())
a = []
dp = [[[] for i in range(10)] for j in range(100)]
for i in range(10):
  dp[0][i] = [i]
  if i != 0:
    a.append(i)
for i in range(1, 10):
  for j in range(10):
    if j != 0:
      for k in dp[i-1][j-1]:
        dp[i][j].append(k + 10 ** i * j)
        a.append(k + 10 ** i * j)
    for k in dp[i-1][j]:
      dp[i][j].append(k + 10 ** i * j)
      if j != 0:
        a.append(k + 10 ** i * j)
    if j != 9:
      for k in dp[i-1][j+1]:
        dp[i][j].append(k + 10 ** i * j)
        if j != 0:
          a.append(k + 10 ** i * j)
print(a[K-1])
### BUGGY CODE ###

import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = np.zeros((h+4, w+4), dtype=np.int8)
for i in range(h):
    s[i+2, 2:-2] = [0 if k == '#' else 1 for k in input()]

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10 ** 12
cost = np.full_like(s, INF, dtype=np.int64)
cost[c[0], c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m:
            continue
        cost[hh, ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if not s[hh, ww] or cost[hh, ww] <= m + 1:
            continue
        cost[hh, ww] = m + 1
        que.append((hh, ww, m + 1))

print(v if (v := cost[d[0], d[1]]) < INF else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

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

dp=[0 for i in range(w+1)]
for q in range(n):
    bq=q
    for i in range(w):
        bi=w-i-1
        if bi+W[bq]<=w:
            dp[bi+W[bq]]=max(dp[bi]+V[bq],dp[bi+W[bq]])
    #print(dp)

print(dp[-1])

### FIXED CODE ###

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

dp=[0 for i in range(w+1)]
for q in range(n):
    bq=q
    for i in range(w):
        bi=w-i-1
        if bi+W[bq]<=w:
            dp[bi+W[bq]]=max(dp[bi]+V[bq],dp[bi+W[bq]])
    #print(dp)

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

x = int(input())

a = int(pow(x, 1/5))

while True:
    if a**5-x<0:
      b = -int(pow(-(a**5-x), 1/5))
    else:
      b = int(pow((a**5-x), 1/5))
      
    if a**5-b**5==x:
      break
    a += 1

print(a, b)

### FIXED CODE ###

x = int(input())
found = False
a = 0
b = 0

for i in range(-200, 201):
  for j in range(-200, 201):
    if i**5-j**5==x:
      found = True
      a = i
      b = j
  if found:
    break
    
print(a, b)
### BUGGY CODE ###

import sys
import math
from collections import deque

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

dp = [[10**9 for _ in range(K)] for _ in range(N)]
dp[0] = [0 for _ in range(K)]

for i in range(N):
    for l in range(K):
        if i-(l+1) >= 0:
            dp[i][l] = min(dp[i - (l + 1)]) + abs(h[i] - h[i - (l + 1)])
        else:
            dp[i][l] = min(dp[i])
print(min(dp[N-1]))

### FIXED CODE ###

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

dp = [[10**9 for _ in range(K+1)] for _ in range(N)]
dp[0] = [0 for _ in range(K+1)]

for i in range(N):
    for l in range(K):
        if i-(l+1) >= 0:
            dp[i][l] = dp[i - (l + 1)][K] + abs(h[i] - h[i - (l + 1)])
        else:
            dp[i][l] = min(dp[i])
        if l == K-1:
            dp[i][K] = min(dp[i])
print(min(dp[N-1]))
### BUGGY CODE ###

import bisect
n,m=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))

for i in range(m):
  a[-1]//=2
  bisect.insort_left(a,a[-1])
  a.pop()
  if a[-1]<1:break
print(sum(a))

### FIXED CODE ###

import heapq
n,m=list(map(int,input().split()))
a=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
  m=heapq.heappop(a)
  heapq.heappush(a, (-m//2)*(-1))
print(-sum(a))
### BUGGY CODE ###

def main():
    from collections import Counter
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    n = int(readline())
    *a, = map(int, readline().split())

    ctr = Counter(a)

    @lru_cache(maxsize=None)
    def prob(c1, c2, c3):
        if c1 == c2 == c3 == 0: return 0

        ret = n
        if c1 > 0:
            ret += c1 * prob(c1 - 1, c2, c3)
        if c2 > 0:
            ret += c2 * prob(c1 + 1, c2 - 1, c3)
        if c3 > 0:
            ret += c3 * prob(c1, c2 + 1, c3 - 1)
        ret /= c1 + c2 + c3
        return ret

    ret = prob(*(ctr[k] for k in range(1, 3 + 1)))
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

N,T=map(int,input().split())
A,B=[],[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
dp=[[[0,0] for i in range(T)] for i in range(N+1)]

for i in range(N):
    for j in range(T):
        if j-A[i]>=0:
            dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j-A[i]][0]+B[i])
            dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j-A[i]][1]+B[i])
        dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0])
        dp[i+1][j][1]=max([dp[i+1][j][1],dp[i][j][0]+B[i],dp[i][j][1]])
ans=max(dp[N][T-1][0],dp[N][T-1][1])
print(ans)

### FIXED CODE ###

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

for i in range(N):
    for j in reversed(range(T)):
        dp[j][1]=max(dp[j][1],dp[j][0]+B[i])
        if j-A[i]>=0:
            dp[j][0]=max(dp[j-A[i]][0]+B[i],dp[j][0])
            dp[j][1]=max(dp[j-A[i]][1]+B[i],dp[j][1])
ans=max(dp[T-1][0],dp[T-1][1])
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
for i in range(N):
  print(A.count(i+1))

### FIXED CODE ###

import collections
N=int(input())
A=[x for x in input().split()]
c = collections.Counter(A)
for i in range(N):
	print(c["{}".format(str(i+1))])
### BUGGY CODE ###

import numpy as np


N = int(input())
inputs = np.array(input().split(), dtype=np.uint8)
inputs = inputs[::-1]
boxes = np.zeros_like(inputs)
M = 0
outputs = []

for i, a in enumerate(inputs):
    num = N - i
    idxs = np.arange(num,  N+1, num) - 1
    S = boxes[idxs].sum()
    if S % 2 != a:
        M += 1
        boxes[num-1] = 1
    # print(num, idxs+1, S, boxes)

print(M)
if M != 0:
    outputs = np.where(boxes == 1)[0] + 1
    outputs = [str(x) for x in outputs]
    print(' '.join(outputs))

### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    B = [0 for _ in range(N)]
    for i in range(N - 1, N // 2 - 1, -1):
        B[i] = A[i]
    for i in range(N // 2 - 1, -1, -1):
        res = 0
        for j in range(i, N, i + 1):
            res += B[j]
        if res % 2 == 0 and A[i] == 1:
            B[i] = 1
        elif res % 2 != 0 and A[i] == 0:
            B[i] = 1

    cnt = 0
    for b in B:
        if b == 1:
            cnt += 1
    print(cnt)
    if cnt > 0:
        res = [i + 1 for i, b in enumerate(B) if b != 0]
        print(*res)
### BUGGY CODE ###

n = int(input())
a = [int(v) for v in input().split()]

field = {}
for v in a:
    if not v in field:
        field[v] = 1
    else:
        field[v] += 1

for i in a:
    if i in field:
        field[i] -= 1
    
    ans = 0
    for k,v in field.items():
        ans += ((v*(v-1))/2)

    print(int(ans))

    if i in field:
        field[i] += 1


### FIXED CODE ###

n = int(input())
a = [int(v) for v in input().split()]

field = {}
for v in a:
    if not v in field:
        field[v] = 1
    else:
        field[v] += 1

all_ans = 0
for k,v in field.items():
    all_ans += ((v*(v-1))/2)


for i in a:
    ans = all_ans
    if i in field:
        n = field[i]
        ans -= (n*(n-1))/2
        n = n - 1
        ans += (n*(n-1))/2
    
    print(int(ans))
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
L = [1]*(N+1)

for i in range(N, -1, -1):

    g = G[i]
    if not g:
        Q[i] = deque()
        continue

    # 子ノードのdequeを集める
    g.sort(key=L.__getitem__, reverse=1)
    k = len(g)
    if k not in PP:
        PP[k] = pow(2, k, MOD)
    e = [PP[k] - k, k, 0]

    g0 = g[0]
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    L[i] = L[g0] + 1
    R = Q[g0]
    for j in g[1:]:
        S = Q[j]

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
    Q[i] = R
if N not in PP:
    PP[N] = pow(2, N, MOD)
ans = PP[N]
for (a0, a1, a2), c in zip(Q[0], C[1:]):
    if N+1-c not in PP:
        PP[N+1-c] = pow(2, N+1-c, MOD)
    ans += PP[N+1-c] * a1 % MOD
print(ans % MOD)


### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

S = input()
L = len(S)
ans = 0
A = [0] * 2020
A[0] = 1
for i in range(L):
     x = int(S[i:]) % 2019
     A[x] += 1

for i in A:
    ans += int(i * (i-1) / 2)

print(ans)

### FIXED CODE ###

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)
### BUGGY CODE ###

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

c = 0
for i in range(N):
    f = True
    pi = P[i]
    for j in range(i):
        if pi>P[j]:
            f = False
            break
    if f:
        c += 1
print(c)

### FIXED CODE ###

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

c = 1
pmin = 1000000
for i in range(1,N):
    if P[i-1]<pmin:
        pmin = P[i-1]
    if pmin >= P[i]:
        c += 1
print(c)
### BUGGY CODE ###

N = int(input())
S = input()

n_total = 0
S_ik, S_jk = [], []
for i in range(0,N-2):
  tmp = []
  for k in range(i+2,N):
    if S[i] != S[k]:
      tmp.append(k)
  S_ik.append(tmp)
for j in range(1,N-1):
  tmp = []
  for k in range(j+1,N):
    if S[j] != S[k]:
      tmp.append(k)
  S_jk.append(tmp)
for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      group1 = list(set(S_ik[i])&set(S_jk[j-1]))
      group2 = list(set([j-i+j])&set(group1))
      if len(group2) == 0:
        n_total += len(group1)
      else:
        n_total += len(group1)-1
print(n_total)

### FIXED CODE ###

N = int(input())
S = input()

n_R, n_G, n_B, n_total = 0, 0, 0, 0
for i in range(N):
  if S[i] == 'R':
    n_R+=1
  elif S[i] == 'G':
    n_G+=1
  else:
    n_B+=1
n_total += (n_R*n_G*n_B)
for j in range(1,N-1):
  i = j-1
  k = j+1
  while 1:
    if 0 <= i and k < N:
      if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
        #print(i,j,k, S[i], S[j], S[k])
        n_total-=1
    else:
      break
    i -= 1
    k += 1
print(n_total)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
m = 1
for i in range(k):
	m *= a[i]
tmp = m
for i in range(k, n):
	m *= a[i]
	m //= a[i - k]
	if m > tmp:
		print('Yes')
	else:
		print('No')
	tmp = m


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k, n):
	if a[i] > a[i - k]:
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

# ダブリング

N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

D = 60

to = [[-1 for i in range(N+1)] for j in range(D)]
to[0] = A

for i in range(1,D):
    for j in range(1,N+1):
        to[i][j] = to[i-1][to[i-1][j]]

ans = 1
for i in range(D):
    if K>>i&1:
        ans = to[i][ans]

print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

visit = [False for i in range(N+1)]
now = 1
cnt = 0
while True:
    if visit[now]:
        break
    visit[now] = True
    now = A[now]
    cnt += 1
cnt2 = 0
visit2 = [False for i in range(N+1)]
while True:
    if visit2[now]:
        break
    visit2[now] = True
    now = A[now]
    cnt2 += 1

if cnt >= K:
    ans = 1
    for i in range(K):
        ans = A[ans]

else:
    K -= cnt
    K = K%cnt2
    ans = now
    for i in range(K):
        ans = A[ans]
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
#from sys import stdin
#import math
#from functools import reduce
    
#A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = input()
 
counter = 0
 
for k in range(N):
    for j in range(k):
        for i in range(j):
            if (j-i)==(k-j):
                continue
            si = S[i]
            sj = S[j]
            sk = S[k]
            if (si==sj):
                continue
            elif (si==sk):
                continue
            elif (sj==sk):
                continue
            counter = counter + 1
 
print(counter)

### FIXED CODE ###

N = int(input())

S = input()

ans = 0


sumR = [0]
sumG = [0]
sumB = [0]

for s in S:
    if s == "R":
        sumR.append(sumR[-1] + 1)
        sumG.append(sumG[-1])
        sumB.append(sumB[-1])
    elif s == "G":
        sumR.append(sumR[-1])
        sumG.append(sumG[-1] + 1)
        sumB.append(sumB[-1])
    elif s == "B":
        sumR.append(sumR[-1])
        sumG.append(sumG[-1])
        sumB.append(sumB[-1] + 1)


for i, s in enumerate(S):
    not_cnt = 0
    for k in range(1, min(i + 1, N - i)):
        L, R = S[i - k], S[i + k]
        if s != L and s != R and L != R:
            not_cnt += 1

    cnt = 0
    if s == "R":
        cnt += sumG[i] * (sumB[-1] - sumB[i + 1])
        cnt += sumB[i] * (sumG[-1] - sumG[i + 1])
    elif s == "G":
        cnt += sumR[i] * (sumB[-1] - sumB[i + 1])
        cnt += sumB[i] * (sumR[-1] - sumR[i + 1])
    elif s == "B":
        cnt += sumG[i] * (sumR[-1] - sumR[i + 1])
        cnt += sumR[i] * (sumG[-1] - sumG[i + 1])

    cnt -= not_cnt
    ans += cnt


print(ans)
### 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,Q = II()
a,b = Line(N-1)
p,x = Line(Q)

for i in range(N-1):
    a[i] -= 1
    b[i] -= 1

for i in range(Q):
    p[i] -= 1


#深さ優先探索
def dfs(pt,v):
    n=len(pt)
    d=[-1]*n
    check_visited = [False]*n
    check_visited[v] = True
    S = [v]
    d[v] = 0
    while S:
        v1 = S.pop()
        for i in pt[v1]:
            if check_visited[i] == False:
                check_visited[i] = True
                d[i] = d[v1] + 1
                S.append(i)
    return d


pt = [[] for _ in range(N)]
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = dfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)

### 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,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


parent = defaultdict(list)
for i in range(N-1):
    parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(1,N):
    val[i] += val[parent[i][0]]

print(*val)
### BUGGY CODE ###

n, k = map(int, input().split())
def cul(x):
    ans = (1 + x)*x/(2*x)
    return ans
p = list(map(cul, list(map(int, input().split()))))
ans = 0
for i in range(n - k + 1):
    cnt = 0
    for j in range(i, i + k):
        cnt += p[j]
    ans = max(ans, cnt)
print(ans)

### FIXED CODE ###

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

def cul(x):
    ans = (1 + x)*x/(2*x)
    return ans

p = list(map(cul, list(map(int, input().split()))))
cnt = sum(p[0:k])
ans = cnt
for i in range(k, n):
    cnt += p[i] - p[i - k]
    ans = max(ans, cnt)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]] = max(d[ab[0]],H[ab[1]-1])
    else:
        d[ab[0]] = H[ab[1]-1]
    if ab[1] in d.keys():
        d[ab[1]] = max(d[ab[1]],H[ab[0]-1])
    else:
        d[ab[1]] = H[ab[0]-1]
    s = s | set(ab)

count = 0
for i in d.keys():
    if H[i-1] > d[i]:
        count += 1

count += N - len(s)

print(count)

### FIXED CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = []

for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]] = max(d[ab[0]],H[ab[1]-1])
    else:
        d[ab[0]] = H[ab[1]-1]
    if ab[1] in d.keys():
        d[ab[1]] = max(d[ab[1]],H[ab[0]-1])
    else:
        d[ab[1]] = H[ab[0]-1]
    s.append(ab[0])
    s.append(ab[1])

count = 0
for i in d.keys():
    if H[i-1] > d[i]:
        count += 1

count += N - len(set(s))

print(count)