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

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7

    # print(A)
    d = dict()
    for i in range(N+1):
        if A[i] not in d: d[A[i]] = [i]
        else: d[A[i]].append(i)

    i1, i2 = 0, 0
    for a in d:
        if len(d[a]) == 2:
            i1, i2 = d[a]
            break
    M = i1 + N-i2
    # print(N, i1, i2)

    B = [1]
    v = 1
    for i in range(1, N+2):
        v = (v*(N-i+2))//i
        B.append(v % div)
    # print(B)

    C = [1]
    v = 1
    for i in range(1, M+1):
        v = (v*(M-i+1))//i
        C.append(v % div)

    for l in range(1, N+2):
        if l <= M+1:
            print((B[l] - C[l-1]) % div)
        else:
            print(B[l])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7

    # print(A)
    d = dict()
    for i in range(N+1):
        if A[i] not in d: d[A[i]] = [i]
        else: d[A[i]].append(i)

    i1, i2 = 0, 0
    for a in d:
        if len(d[a]) == 2:
            i1, i2 = d[a]
            break
    M = i1 + N-i2
    # print(N, i1, i2)

    # N+1_C_l
    pow1 = [1, 1]
    for i in range(2, N+2):
        pow1.append(pow1[-1]*i % div)

    # pow2 = [1, 1]
    # for i in range(2, N+2):
    #     j = powquick(i, div-2, div)
    #     pow2.append(pow2[-1]*j % div)

    pow2 = [1, 1]
    inv = [0, 1]
    for i in range(2, N+2):
        inv.append((-inv[div % i]) *(div // i) % div)
        pow2.append(pow2[-1] * inv[-1] % div)

    for l in range(1, N+2):
        v = (pow1[N+1]*pow2[l]*pow2[N+1-l]) % div
        # print(v)
        if l <= M+1:
            v -= (pow1[M]*pow2[l-1]*pow2[M-l+1]) % div
        print(v % div)

def powquick(x, y, div):
        if y == 0: return 1
        if y == 1: return x % div
        if y % 2 == 0: return pow(powquick(x, y // 2, div), 2) % div
        if y % 2 == 1: return pow(powquick(x, y// 2, div), 2) * x % div


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

import itertools

k,s=map(int,input().split())
K=list(range(k+1))
ans=0
for team in itertools.product(K,repeat=3):
    if sum(team)==s:
        ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
        if 0<=s-i-j<=k:
            ans+=1
print(ans)
### BUGGY CODE ###

import bisect

n,m = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()

for i in range(m):
    b,c = map(int,input().split())
    pos = bisect.bisect_left(lst,c)
    for j in range(min(b,pos)):
        lst[j] = c
    lst.sort()
print(sum(lst))

### FIXED CODE ###

n,m = map(int,input().split())
l_a = sorted(list(map(int,input().split())))
l_bc = [list(map(int,input().split())) for _ in range(m)]
l_bc.sort(key = lambda x:x[1],reverse = True)
for b,c in l_bc:
    l_a.extend([c]*b)
    if len(l_a) > 2*n:
        break

l_a.sort(reverse = True)
print(sum(l_a[:n]))
### BUGGY CODE ###

# @author 

import sys

class OMatching:
    def solve(self):
        from collections import defaultdict

        MOD = 10 ** 9 + 7

        n = int(input())
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        dp = [[0] * ((1 << n) + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        by_1 = defaultdict(list)
        for j in range(1 << n):
            by_1[bin(j).count('1')].append(j)
            
        for i in range(1, n + 1):
            for j in by_1[i - 1]:
                for k in range(n):
                    if (j >> k) & 1 or a[i - 1][k] == 0:
                        continue
                    dp[i][j | (1 << k)] += dp[i - 1][j]
                    dp[i][j | (1 << k)] %= MOD

        # [print(item) for item in dp]

        print(sum(dp[n]))

solver = OMatching()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class OMatching:
    def solve(self):
        from collections import defaultdict

        def numberOfSetBits(i):
            i = i - ((i >> 1) & 0x55555555)
            i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
            return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

        MOD = 10 ** 9 + 7

        n = int(input())
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])


        dp = [[0] * ((1 << n) + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        by_1 = defaultdict(list)
        for j in range(1 << n):
            by_1[numberOfSetBits(j)].append(j)
        # for j in range(1 << n):
        #     by_1[bin(j).count('1')].append(j)

        for i in range(1, n + 1):
            for j in by_1[i - 1]:
                for k in range(n):
                    if (j >> k) & 1 or a[i - 1][k] == 0:
                        continue
                    dp[i][j | (1 << k)] += dp[i - 1][j]
                    dp[i][j | (1 << k)] %= MOD

        # [print(item) for item in dp]

        print(sum(dp[n]))

solver = OMatching()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

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

@jit
def main():
    n=int(input().rstrip())
    a=sorted([int(i) for i in input().split()])
    maxn=10**6+1
    dp=[True]*(maxn)
    cnt=[0]*(maxn)
    ans=0
    for i in a:
        if dp[i]:
            cnt[i]+=1
            for j in range(i*2,maxn,i):
                dp[j]=False

    for i in a:
        if dp[i] and cnt[i]==1:
            #print(i)
            ans+=1
    print(ans)

if __name__=="__main__":main()

### FIXED CODE ###

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

N=int(input().rstrip())
a=[int(i) for i in input().split()]
l=max(a)+1
cnt=[0]*l
for i in a:
    for j in range(i,l,i):cnt[j]+=1

ans=0
for i in a:
    if cnt[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n, x, m = map(int, input().split())
    d2 = [d[i] % m for i in range(k)]
    a = (n - 1) // k
    b = (n - 1) % k
    c = (x + sum(d2) * a + sum(d2[:b])) // m - (x // m)
    print(n - 1 - c - d2.count(0) * a - d2[:b].count(0))

### FIXED CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n, x, m = map(int, input().split())
    d2 = [d[i] % m for i in range(k)]
    sum_d = [0] * (k + 1)
    count_d = [0] * (k + 1)
    for i in range(k):
        sum_d[i + 1] = sum_d[i] + d2[i]
        if d2[i] == 0:
            count_d[i + 1] = count_d[i] + 1
        else:
            count_d[i + 1] = count_d[i]
    a = (n - 1) // k
    b = (n - 1) % k
    c = (x + sum_d[k] * a + sum_d[b]) // m - (x // m)
    print(n - 1 - c - count_d[k] * a - count_d[b])
### BUGGY CODE ###

n=input()
s=''
for i in range(n):
	s+=raw_input()
s+=s
result=0
for shift in xrange(n):
	ok=True
	for i in xrange(n):
		if not ok:
			break
		j=0
		while j<n:
			if s[(i+shift)*n+j]!=s[(j+shift)*n+i]:
				ok=False
				break
			j+=1
	if ok:
		result+=n
print result

### FIXED CODE ###

n=input()
s=[raw_input() for i in range(n)]
t=[]
for i in range(n):
	t+=[s[j][i] for j in xrange(n)]*2
s+=s
s=''.join(s)
#print s
t=''.join(t)
#print t
result=0
for shift in xrange(n):
	ok=True
	for i in xrange(n):
		if s[(i+shift)*n: (i+shift)*n+n]!=t[i*n*2+shift: i*n*2+shift+n]:
			ok=False
			break
	if ok:
		result+=n
print result
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def mod_fra(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def mod_power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return mod_power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * mod_power(n, r-1, mod) % mod

def mod_comb(n, k, mod):
    a=mod_fra(n, mod)
    b=mod_fra(k, mod)
    c=mod_fra(n-k, mod)
    return (a * mod_power(b, mod-2, mod) * mod_power(c, mod-2, mod)) % mod
def main():
    n,m,k=map(int,input().split())
    mod=998244353
    ans=0
    for kx in range(k+1):
        ans+=mod_comb(n-1,kx,mod)*m*(m-1)**(n-1-kx)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
class Facts:
  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      setup_table(n_max) 
  
  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
  
  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[self.mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=Facts(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.cmb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)


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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l)
sys.stdout.flush()
ltmp = STR()
if ltmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c)
    sys.stdout.flush()
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if (c - l) % 2 == 0:
        if tmp == ltmp:
            l = c
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(n - 2):
    for j in range(1, n - 1):
        for k in range(2, n ):
            if i < j:
                if j < k:
                    if j - i != k - j:
                        if s[i] != s[j]:
                            if s[i] != s[k]:
                                if s[j] != s[k]:
                                    ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

comb = r*g*b

for i in range(1, n - 1):
    for j in range(2, n):
        if i < j:
            if (2*j - i) <= n:
                if s[i - 1] != s[j - 1]:
                    if s[i - 1] != s[2*j - i - 1]:
                        if s[j - 1] != s[2*j - i - 1]:
                            comb -= 1

print(comb)
### BUGGY CODE ###

num = int(input())

arr = []

for i in range(num):
    arr.append(int(input()))

for i in range(num):
    if i == 0:
        print(int(max(arr[1:])))
    elif i == num-1:
        print(int(max(arr[:-1])))
    else:  
        print(int(max(arr[:i]+arr[i+1:])))

### FIXED CODE ###

from collections import deque

num = int(input())

arr = []

for i in range(num):
    arr.append(int(input()))

arr0 = sorted(arr,reverse=True)
arr00 = arr0[0]
arr01 = arr0[1]

for i in range(num):
    if arr[i] != arr00:
        print(arr00)
    else:
        print(arr01)
### BUGGY CODE ###

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

B = []

for i in range(n):
  if i %2:
    B = [A[i]] + B
  else:
    B = B + [A[i]]
    
if n%2:
  B = B[::-1]
print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
from collections import deque

B = deque([])

for i in range(n):
  if i %2:
    B.appendleft(A[i])
  else:
    B.append(A[i])
B = list(B)
if n%2:
  B = B[::-1]
print(*B)
### BUGGY CODE ###


n,m  = map(int,input().split())
ln = []
mod_1 = 10**9 + 7
for i in range(m):
    ln.append(int(input()))
line = []
for i in range(n+1):
    if  i in ln:
        line.append(0)
    elif i == 0:
        line.append(1)
    elif i == 1:
        line.append(1)
    else:
        line.append((line[-1] + line[-2]) % mod_1)
print(line[-1])



### FIXED CODE ###

#dp
n,m  = map(int,input().split())
ln = [-1 for i in range(n +1)]
mod_1 = 10**9 + 7
for i in range(m):
    ln[int(input())] = 0
#print(ln)
for i in range(n+1):
    if ln[i] ==0:
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        ln[i] = (ln[i-1] + ln[i-2]) % mod_1
#print(ln)
print(ln[-1])
### BUGGY CODE ###

L,R=map(int,input().split())

x=[]
for i in range(L,R):
    for j in range(L+1,R+1):
        y=((i*j)%2019)
        x.append(y)

print(min(x))

### FIXED CODE ###

L,R=map(int,input().split())

x=[]
a=0
for i in range(L,R):
    for j in range(L+1,R+1):
        y=((i*j)%2019)
        x.append(y)
        if y==0:
            break
    if y==0:
            break

print(min(x))
### BUGGY CODE ###

# EDPC A Frog 1
N, K = map(int, input().split())
H = list(map(int,input().split()))

cost = [float("inf")]*N
cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,K+1):
        if i - k < 0:
            break
        cost[i] = min(cost[i],cost[i-k]+abs(H[i]-H[i-k]))

print(cost[N-1])

### FIXED CODE ###

# EDPC B Frog 2
N, K = map(int, input().split())
H = list(map(int,input().split()))

cost = [float("inf")]*N
cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,min(K,i)+1):
        cost[i] = min(cost[i], cost[i-k]+abs(H[i]-H[i-k]))

print(cost[N-1])
### BUGGY CODE ###

A, B, N = [int(i) for i in input().split()]
ans = 0
for i in range(B):
    x = N - i
    if x < 0:
        break
    tmp = int(A * (x % B / B) - (A * x % B) / B)
    if tmp >= ans:
        ans = tmp
print(ans)

### FIXED CODE ###

A, B, N = [int(i) for i in input().split()]
ans = 0
if N < B:
    ans = int(( A * (N % B) - (A * N) % B) / B)
else:
    tmp_ = int(( A * (N % B) - (A * N) % B) / B)
    x = (N - N % B - 1)
    tmp = int(( A * (x % B) - (A * x) % B) / B)
    ans = max(tmp, tmp_)
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
maxketa = max([len(bin(a[i])) for i in range(n)])-2
array = [[(a[j]>>i) & 1 for j in range(n)] for i in range(maxketa)]
"""
arrayは逆順に並んでることに注意
"""
mod = 10**9+7
tmparrayc = [Counter(array[i]) for i in range(maxketa)]
ans = sum([tmparrayc[i][0]*tmparrayc[i][1]*(2**i) % mod for i in range(maxketa)]) % mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
maxketa = max([len(bin(a[i])) for i in range(n)])-2
mod = 10**9+7
ans = 0
for i in range(maxketa):
	ones = 0
	for j in range(n):
		if (a[j] >> i) & 1:
			ones += 1
	ans = (ans + (n-ones)*ones*(2**i)) % mod
 
print(ans)
### BUGGY CODE ###


n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
a=[]
p=1
while p not in a:
    a.append(p)
    p=m[p-1]

l=a.index(p)

if k<len(a):
    print(a[k])
else:
    k-=l
    print(a[l+k%(len(a)-l)])

            
            
        
    

### FIXED CODE ###


n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
a=[]
p=1
vis=[0]*n
while vis[p-1]==0:
    a.append(p)
    vis[p-1]=1
    p=m[p-1]

l=a.index(p)

if k<len(a):
    print(a[k])
else:
    k-=l
    print(a[l+k%(len(a)-l)])
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))
sum = 0
for i in range(N-1):
    for m in range(i+1, N):
        sum += A[i]*A[m]

if sum < 1000000007:
    print(sum)
else:
    print(sum%1000000007)

### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))
S = sum(A)
ans = 0
for i in range(N):
    S -= A[i]
    ans += A[i] * S
    

ans = ans % (10 ** 9  +7)        

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

n = input()
st = input()

N = n.split(' ')[0]
Q = int(n.split(' ')[1])

for i in range(0, Q):
    n = input()
    l = int(n.split(' ')[0])
    r = int(n.split(' ')[1])
    partial = st[l-1:r]
    count = 0
    for i in range(0, len(partial) - 1):
        AC = partial[i:i+2]
        if AC == 'AC':
            count += 1

    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for i in range(q)]

cum=[0]*n
for i in range(1, n):
    cum[i] = cum[i - 1]
    if s[i-1:i+1] == 'AC':
        cum[i]+=1

for i in range(q):
    print(cum[a[i][1]-1]-cum[a[i][0]-1])
### BUGGY CODE ###

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

S = [0]
for i in range(N):
        S.append(S[i]+A[i])

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        a_tmp = []
        if S[a_before] > S[b] - S[a_before]:
                a_tmp.append(a_before)
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                a_tmp.append(i)
                                a_tmp.append(i-1)
                                a_before = i-1
                                break
                else:
                        a_tmp.append(b-1)
                        a_before = b-1

        c_tmp = []
        if S[c_before] - S[b] > S[N] - S[c_before]:
                c_tmp.append(c_before)
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                c_tmp.append(i)
                                c_tmp.append(i-1)
                                c_before = i-1
                                break
                else:
                        c_tmp.append(N-1)
                        c_before = N-1

        for a in a_tmp:
                for c in c_tmp:
                        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

### FIXED CODE ###

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

S = [0]
for i in range(N):
        S.append(S[i]+A[i])

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        if S[a_before] > S[b] - S[a_before]:
                a=a_before
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                if abs(S[b]-S[i-1]-S[i-1]) < abs(S[b]-S[i]-S[i]):
                                        a=i-1
                                        a_before = i-1
                                        break
                                else:
                                        a=i
                                        a_before = i
                                        break
                else:
                        a=b-1
                        a_before = b-1

        if S[c_before] - S[b] > S[N] - S[c_before]:
                c=c_before
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                if abs((S[N]-S[i-1]) - (S[i-1]-S[b])) < abs((S[N]-S[i]) - (S[i]-S[b])):
                                        c=i-1
                                        c_before = i-1
                                        break
                                else:
                                        c=i
                                        c_before = i
                                        break
                else:
                        c=N-1
                        c_before = N-1

        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

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

ans = [0] * n
searched = set()
def dfs(cur, c):
    c += cost[cur]
    ans[cur] = c
    searched.add(cur)
    for next in edge[cur]:
        if next not in searched:
            dfs(next, c)

dfs(0, 0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

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

ans = [0] * n
def dfs(me, parent, cum):
    cum += counter[me]
    ans[me] = cum
    for child in connect[me]:
        if child != parent:
            dfs(child, me, cum)

dfs(0, -1, 0)

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

n, k = map(int, input().split())
s = set()
for i in range(k):
    l,r = list(map(int, input().split()))
    L = [i for i in range(l,r+1)]
    s = set(L+list(s))
dp=[0]*(n+1)
dp[1] = 1
p = 998244353

for i in range(1, n):
    for j in s:
        if i+j > n:
            continue
        dp[i+j] += (dp[i])
        dp[i+j] %= p

print(dp[n] % p)

### FIXED CODE ###

n, k = map(int, input().split())
dp=[0]*(n+1)
dp[1] = 1

rui=[0]*(n+1)
rui[1] = 1
p = 998244353
lr=[]
for i in range(k):
    lr.append(list(map(int, input().split())))

for i in range(2,n+1):
    for l, r in lr:
        dp[i] += rui[max(i-l, 0)] - rui[max(i-r-1, 0)]
        dp[i] %= p
    rui[i] = rui[i-1] + dp[i]
    rui[i] %= p
print(dp[n])
### BUGGY CODE ###

N = int(input())
Al = input().split()

A = []
for i in range(N):
  A.append(int(Al[i]))

num = 0
ma = 10**9 + 7

for i in range(N):
  num = (num + A[i]*sum(A[i+1:])) % ma

print(num)


### FIXED CODE ###

N = int(input())
Al = input().split()
A = list( map((lambda x: int(x)), Al))
num = 0
ma = 10**9 + 7
li = 0

for i in range(N-1, 0, -1):
  li += A[i]
  num += A[i-1] * li

num = num % ma
print(num)
### BUGGY CODE ###

import numpy as np

N = int(input())
S = input()
L = [0] * N
for i in range(N):
    if S[i] == "#":
        # white
        L[i] = 1
    else:
        L[i] = 0
L = np.array(L, dtype=np.int8)
L2 = np.zeros(N, dtype=np.int8)

ans = np.abs((L - L2)).sum()
for i in range(N):
    L2[N-1-i] = 1
    ans_tmp = np.abs((L - L2)).sum()
    ans = min(ans, ans_tmp)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
L = [0] * N
for i in range(N):
    if S[i] == "#":
        L[i] = 1
    else:
        L[i] = 0

leftblack = 0
rightwhite = len([x for x in L if x == 0])
ans = leftblack + rightwhite

for i in range(N):
    if S[i] == "#":
        leftblack += 1
    else:
        rightwhite -=1
    ans = min(ans, leftblack + rightwhite)
print(ans)