Harryxun/stf_run huggingface dataset:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,n):
        for y in range(1,n):
            for z in range(1,n):
                if x*x+y*y+z*z+x*y+y*z+x*z-1 >= n+1:
                    break
                ans[x*x+y*y+z*z+x*y+y*z+x*z-1] += 1
    for i in range(n):
        print(ans[i])
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,n):
        for y in range(1,n):
            for z in range(1,n):
                if x*x+y*y+z*z+x*y+y*z+x*z >= n+1:
                    break
                ans[x*x+y*y+z*z+x*y+y*z+x*z-1] += 1
    for i in range(n):
        print(ans[i])
if __name__ == "__main__":
    main()
n=int(input())
a=list(map(int,input().split()))

ra=list(reversed(a))

left=[]
right=[]
right.append(ra[0])
left.append(a[0])

if n>2:
  import math
  left.append(math.gcd(a[0],a[1]))
  for i in range(2,n-1):
    k=math.gcd(k,a[i])
    left.append(k)

  right.append(math.gcd(ra[0],ra[1]))
  for i in range(2,n-1):
    k=math.gcd(k,ra[i])
    right.append(k)

  print(left)
  print(right)
  ans=[right[-1]]
  for i in range(1,n-1):
    ans.append(math.gcd(left[i-1],right[len(left)-i-1]))
  ans.append(left[-1])
  print(max(ans))
else:
  print(max(ra[0],a[0]))

### FIXED CODE ###

import math
n=int(input())
a = list(map(int,input().split()))
a.sort()
lr=[0]*n
rl=[0]*n

for i in range(n):
  if i==0:
    g=a[0]
    lr[0]=g
  else:
    g=math.gcd(a[i],g)
    lr[i]=g
    
for i in range(n-1,0,-1):
  if n-1==i:
    g=a[n-1]
    rl[n-1]=g
  else:
    g=math.gcd(a[i],g)
    rl[i]=g  
hantei=0
ans=0
#print(lr)
#print(rl)
for i in range(n):
  if i==0:
    hantei=rl[1]
  elif i==n-1:
    hantei=lr[n-2]
  else:
    hantei=math.gcd(lr[i-1],rl[i+1])
  if ans<=hantei:
    ans=hantei
    
print(ans)
H, N = map(int, input().split())
A = map(int, input().split())
Ans = 0

for x in A:
  Ans += x
  
if(Ans >= H):
  print(`Yes`)
else:
  print(`No`)

### FIXED CODE ###

H, N = map(int, input().split())
A = map(int, input().split())
Ans = 0
 
for x in A:
  Ans += x
  
if Ans >= H:
  print('Yes')
else:
  print('No')
import math

N = int(input())

for h in range(math.ceil(N/4),3501):
    for n in range(math.ceil(1/(4/N-1/h)),3501):
        a = 4/N - 1/h - 1/n
        if a!= 0:
            w = 1/a
            if 4*h*n*w == N*(h*n+n*w+w*h):
                break
    else:
        continue
    break

print(h,n,int(w))

### FIXED CODE ###

N = int(input())
for h in range(max(1, N//4), 3501):
    if 4*h - N > 0:
        for n in range(max(1, N * h // (4*h-N)), 3501):
            if 4*h*n - (h+n)*N > 0 and h*n*N % (4*h*n - (h+n)*N) == 0:
                print(h, n, h*n*N // (4*h*n - (h+n)*N))
                exit()
n, m = map(int, input().split())
a = map(int, input().split())
a = sorted(a)
a.reverse()
min_sum = 0
ti = 0
if m % 2 == 1:
  ti = m // 2 + 1
else:
  ti = m // 2

for _a in a:
  if m > 0:
    min_sum += _a // (2 ** ti)
    ti -= 1
  else:
    min_sum += _a

print(min_sum)

### FIXED CODE ###

# 最小金額を求める
# 一番高い商品に割引を適用して半額（小数点以下切り捨て）にする作業の繰り返し
# 問題詳細：https://atcoder.jp/contests/abc141/tasks/abc141_d
# 優先度付きキューを利用する
import heapq

def main():
  n, m = map(int, input().split())
  a = list(map(int, input().split()))
  pq = to_priorityqueue(a)
  pq = use_ticket(pq, m)
  print(-sum(pq))


# 優先度付きキューを作成
# heapqモジュールを利用
# pythonのheapqの場合、pop(取り出し)を行った際に最小のものから取り出される
# 今回は大きい順に取り出して利用したいため、-1を掛けてpushする（最大の値が最小になる）
def to_priorityqueue(list):
  rtn = []
  for el in list:
    heapq.heappush(rtn, -el)
  return rtn

# チケットの利用（割引の適用）
# チケットがなくなるまで、その時点で最も価格が高い商品にわりびきを適用する
# 最大まで割引を適用した結果できたキューを返す
def use_ticket(pq, t_num):
  while t_num and pq:
    el = -(heapq.heappop(pq))
    el //= 2
    heapq.heappush(pq, -el)
    t_num -= 1
  return pq

if __name__ == "__main__":
  main()
s = str(input())
a = []
 
for i in len(s):
    if s[i] == '0':
        a.append('0')
    elif s[i] == '1':
        a.append('1')
    else:
        if len(a) != 0:
            a.pop()
 
print(''.join(a))

### FIXED CODE ###

s = str(input())
a = []
 
for i in range(len(s)):
    if s[i] == '0':
        a.append('0')
    elif s[i] == '1':
        a.append('1')
    else:
        if len(a) != 0:
            a.pop()
 
print(''.join(a))
import math

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

for i in A:
  l.append(math.log10(A[i]))
  
if sum(l)<18:
  print(int(10**sum(l)))
else:
  print(-1)

### FIXED CODE ###

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

if 0 in a:
  print(0)

else:
  ans = 1
  for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
      print(-1)
      exit()
  print(ans)
import collections
w, h, x, y = map(int, input().split())
area = []
# xの直線
area.append(min(h*x, h*(w-x)))

# yの直線
area.append(min(w*y, w*(h-y)))

# 角たち
a = w * h
tmp = h**2 * x / y
area.append(min(tmp, a - tmp))
tmp = w**2 * y / x
area.append(min(tmp, a - tmp))
tmp = w**2 * y / (w - x)
area.append(min(tmp, a - tmp))
tmp = h**2 * x / (h - y)
area.append(min(tmp, a - tmp))

ans_c = collections.Counter(area)

ans = sorted(ans_c.items(), reverse=True)[0]
size = ans[0]
a = 0
if ans[1] > 1:
    a = 1

print("{} {}".format(size, a))


### FIXED CODE ###

import collections
w, h, x, y = map(int, input().split())

ans = 0
if x + x == w and y + y == h:
    ans = 1

print("{} {}".format(w * h / 2, ans))
def available(start, end, S, step=None):
    if step is not None:    #   追い越し処理
        S = S[:step] + "#" + S[step+1:]
    for i in range(start-1, end-1):
        if S[i] == "#" and S[i+1] == "#":
            return False
    return True, S
    
def overtake(start, end, S):
    for i in range(start-1, end-1):
        if S[i-1] == "." and S[i] == "." and S[i+1] == ".":
            step = i
            return True, step
    return False, None

N, A, B, C, D = map(int, input().split())
S = input()

if D > C:   #   追い越しが不要な時
    judge1, S = available(A, C, S)
    judge2, S = available(B, D, S)
    if judge1 and judge2:
        print("Yes")
    else:
        print("No")
else:   #   追い越しが必要な時
    overtakable, step = overtake(B, D, S)
    if overtakable:   #   追い越しが可能な時
        judge1, S = available(B, D, S, step=step)
        judge2, S = available(A, C, S)
        if judge1 and judge2:
            print("Yes")
        else:
            print("No")
    else:   #   追い越しができない時
        print("No")
        

### FIXED CODE ###

def available(start, end, S, step=None):
    if step is not None:    #   追い越し処理
        S = S[:step] + "#" + S[step+1:]
    for i in range(start, end):
        if S[i] == "#" and S[i+1] == "#":
            return False, S
    return True, S
    
def overtake(start, end, S):
    for i in range(start, end+1):
        if S[i-1] == "." and S[i] == "." and S[i+1] == ".":
            step = i
            return True, step
    return False, None

N, A, B, C, D = map(int, input().split())
S = "." + input() + "."

if D > C:   #   追い越しが不要な時
    judge1, S = available(A, C, S)
    judge2, S = available(B, D, S)
    if judge1 and judge2:
        print("Yes")
    else:
        print("No")
else:   #   追い越しが必要な時
    overtakable, step = overtake(B, D, S)
    if overtakable:   #   追い越しが可能な時
        judge1, S = available(B, D, S)
        judge2, S = available(A, C, S, step=step)
        if judge1 and judge2:
            print("Yes")
        else:
            print("No")
    else:   #   追い越しができない時
        print("No")
s=int(input())

print(n**3)


### FIXED CODE ###

n=int(input())

print(n**3)
import numpy as np
import itertools
N, M = map(int, input().split())
x = [0] * N
y = [0] * N
z = [0] * N
for i in range(N):
    x[i], y[i], z[i] = map(int, input().split())

x = np.array(x)
y = np.array(y)
z = np.array(z)

ans = 0
vals = []
for op1,op2,op3 in itertools.product([-1,1],repeat=3):
    #print(op1,op2,op3)
    s = x*op1 + y*op2 + z*op3
    #print(s)
    s.sort()
    vals.append(s[-M:].sum())


print(max(vals))

### FIXED CODE ###

import numpy as np
import itertools
N, M = map(int, input().split())
x = [0] * N
y = [0] * N
z = [0] * N
for i in range(N):
    x[i], y[i], z[i] = map(int, input().split())

x = np.array(x)
y = np.array(y)
z = np.array(z)

ans = 0
vals = []
for op1,op2,op3 in itertools.product([-1,1],repeat=3):
    #print(op1,op2,op3)
    s = x*op1 + y*op2 + z*op3
    #print(s)
    s.sort()
    vals.append(s[N-M:].sum())


print(max(vals))
N, K = map(int,input.split())
S = input()
ans = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    ans += 1
print(min(N-1, ans + 2 * K))

### FIXED CODE ###

N, K = map(int,input().split())
S = input()
ans = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    ans += 1
print(min(N-1, ans + 2 * K))
A,B,C=int(input())
if A==B and A!=C:
  print("Yes")
elif B==C and B!=A:
  print("Yes")
elif C==A and C!=B:
  print("Yes")
else:
  print("No")
  


### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b and a!=c:
  print("Yes")
elif b==c and b!=a:
  print("Yes")
elif c==a and c!=b:
  print("Yes")
else:
  print("No")
x = list(map(int,input().split()))

print(x.index("0")+1)

### FIXED CODE ###

x = list(map(int,input().split()))
 
print(x.index(0)+1)
from collections import defaultdict
from operator import mul
from functools import reduce
def p(n,r):
  if r==0:
    return 1
  return reduce(mul, range(n, n-r, -1))
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)
log = [1]*N

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]

stuck = [a-1]
log[a-1] = 0
ans = K
while stuck:
  e = stuck.pop()
  n = 0
  for c in es[e]:
    if log[c]:
      stuck += [c]
      n += 1
      log[c] = 0
  if e==a-1:
    ans *= p(K-1, n)
  elif K-2<n:
    ans *= 0
    break
  else:
    ans *= p(K-2, n)
  ans %= MOD
print(ans)

### FIXED CODE ###

from collections import defaultdict, deque
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
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 )

N, K = map(int, input().split())
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

log = [float('inf')]*N
log[0] = 0
q = deque([0])
ans = K
while q:
  p = q.popleft()
  if log[p]<1:
    ans *= cmb(K-1,K-1-len(dic[p]),mod)
  else:
    ans *= cmb(K-2,K-1-len(dic[p]),mod)
  ans %= mod
  for e in dic[p]:
    if log[e]>log[p]+1:
      q += [e]
      log[e] = log[p]+1
print(ans)
print(input()*input()/2)

### FIXED CODE ###

a,b,c = map(int, input().split())
print(a*b//2)
N = input()
satisfied_pattern = 10**N - (2*(9**N) - 8**N)
output = satisfied_pattern % (10**9+7)
print(output)


### FIXED CODE ###

from sys import stdin
N = stdin.readline().rstrip()
N = int(N)
satisfied_pattern = 10**N - (2*(9**N) - 8**N)
output = satisfied_pattern % (10**9+7)
print(output)
n = int(input())
d = map(int, input().split())
s = 0
for i in range(n):
    for j in range(n):
        if i != j:
            s += d[i] * d[j]
print(int(s/2))

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
s = 0
for i in range(n):
    for j in range(n):
        if i != j:
            s += d[i] * d[j]
print(int(s/2))
a, b, c = map(int, input().split(""))
if a < b < c:
 print ("Yes")
else:
 print ("No")

### FIXED CODE ###

a, b, c = map(int, raw_input().split())
if a < b and b < c:
 print "Yes"
else:
 print "No"
def solve():
  s=input()
  for l in range(len(s)):
    for r in range(l,len(s)):
      if "keyence" in a[:l]+a[r:]:
        print("YES")
        return
  print("NO")

solve()

### FIXED CODE ###

def solve():
  s=input()
  for l in range(len(s)):
    for r in range(l,len(s)+1):
      if "keyence"==s[:l]+s[r:]:
        print("YES")
        return
  print("NO")

solve()
N=int(input())
List=list(map(int,input().split()))
c=0
for i in range(N-1):
  for j in range(i+1,N):
    c=c+(List[i]*List[j])
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
c=a-2*b
if c<=0:
    print(0)
else:
    print(c)
def main():    
    n,m = map(int,input().split())

    a_list = list(map(int,input().split()))
    total = 0

    for i in range(m):
        b,c = map(int,input().split())
        a_list.extend([c]*b)

    a_list.sort(reverse=True)
    print(sum(a_list[:n]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

a,b = map(int, input().split())


if a<=5:
    fee = 0
elif a>=13:
    fee = b
else:
    fee = b//2

print(fee)
n = input().strip()
m = int(n)
a = int(len(m))
for i in range(a):
  if i == 7:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n =list(map(int, input().strip()))

if 7 in n:
  print('Yes')
else:
  print('No')
#!/usr/bin/env python3
#ABC140 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
s = list(input())
l = []
cnt = 1
for i in range(1,n):
    if s[i-1] != s[i]:
        l.append((cnt,i-1))
        cnt = 0
    cnt += 1
l.append((cnt,i))
m = len(l)
h = []
for i in range(m):
    if i == 0:
        heappush(h,(-(l[i][0]+l[i+1][0]),l[i][0],l[i][1]))
    elif i == m-1:
        heappush(h,(-(l[i][0] + l[i-1][0]),l[i][0],l[i][1]))
    else:
        heappush(h,(-(l[i][0] + l[i-1][0] + l[i+1][0]),l[i][0],l[i][1]))
for _ in range(min(k,len(h))):
    l,i,j = heappop(h)
    if s[j] ==  'R':
        s[j-i+1:j+1] = 'L'*i
    else:
        s[j-i+1:j+1] = 'R'*i
ans = 0
for i in range(n):
    if s[i] == 'L':
        if i > 0:
            if s[i-1] == 'L':
                ans += 1
    else:
        if i < n-1:
            if s[i+1] == 'R':
                ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC140 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
s = input()
x,y = 0,0
for i in range(1,n):
    if s[i] == s[i-1]:
        x += 1
    else:
        y += 1
print(x + min(y,2*k))
n = int(input())
total = 0
val1 = int(math.ceil(math.log(n,10)))
ans = 0
if val1==1:
	ans = n
elif val1==2:
    ans = 9
elif val1==3:
	ans = 9+n-99
elif val1==4:
	ans = 909
elif val1==5:
	ans = 909+n-9999
else:
	ans = 90909
if val1==math.log(n,10) and val1%2:
	print(ans-1)
else:
	print(ans)

### FIXED CODE ###

import math
n = int(input())
total = 0
word = str(n)
val1 = len(word)
ans = 0
if val1==1:
	ans = n
elif val1==2:
    ans = 9
elif val1==3:
	ans = 9+n-99
elif val1==4:
	ans = 909
elif val1==5:
	ans = 909+n-9999
else:
	ans = 90909
print(ans)
a = int(input())
b = int(input())
c = int(input())

top = b // c
if a%c == 0:
  bottom = a//c - 1
else:
  bottom = a//c

print(top-bottom)

### FIXED CODE ###

a,b,c = map(int, input().split())

top = b // c
if a%c == 0:
  bottom = a//c - 1
else:
  bottom = a//c

print(top-bottom)
S1, S2, S3 = map(int,input().split())
S = S1 + S2 + S3

print(str(S))

### FIXED CODE ###

s = input()
print(s.count("1"))
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

# INPUT
n, x = map(int, input().split())
capitals = list(map(int, input().split()))

# PROCESS
distance_cap = list(map(lambda c: abs(x-c), capitals))
answer = gcd_list(distance_cap)

# OUTPUT
print(answer)




### FIXED CODE ###

from fractions import gcd
from functools import reduce

def gcds(*numbers):
    return reduce(gcd, numbers)

def gcd_list(numbers):
    return reduce(gcd, numbers)

# INPUT
n, x = map(int, input().split())
capitals = list(map(int, input().split()))

# PROCESS
distance_cap = list(map(lambda c: abs(x-c), capitals))
answer = gcd_list(distance_cap)

# OUTPUT
print(answer)
print((int)input()/3)

### FIXED CODE ###

print(int(input())//3)
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[0]<=A[it+1] and A[it]<=A[it+1]:
            it+=1
        else: it = 0
    if it == N-1:
        it = 0
    print(A)
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
a = input()
l=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
if len(set(a))==26:
  pritn('None')
else:
  for i in range(len(l)):
    if l[i] not in a:
      print(l[i])
      exit()

### FIXED CODE ###

a = input()
l=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
if len(set(a))==26:
  print('None')
else:
  for i in range(len(l)):
    if l[i] not in a:
      print(l[i])
      break
N = int(input())

total = 0
A = []
for i in range(N):
    a = int(input())
    total += a
    A.append(a)

mod = 998244353

dp = [[0]*91000 for i in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for j in range(300*i, -1, -1):
        dp[i][j+A[i-1]] += dp[i-1][j]
        dp[i][j+A[i-1]] %= mod
        dp[i][j] += 2*dp[i-1][j]
        dp[i][j] %= mod

exc = 0
for j in range((total+1)//2, total+1):
    exc += dp[N][j]
    exc %= mod

res = (3**N % mod) - exc * 3

if total % 2 == 0:
    dp = [[0]*91000 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(300*i, -1, -1):
            dp[i][j+A[i-1]] += dp[i-1][j]
            dp[i][j+A[i-1]] %= mod
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
    res += dp[N][total/2] * 3

print(res % mod)

### FIXED CODE ###

import numpy as np

mod = 998244353
N = int(input())
a = np.array([int(input()) for i in range(N)])
sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0,0] = 1

for i in range(1, N+1):
    a_i = a[i-1]
    dp[i,a_i:] += dp[i-1,:-a_i]
    dp[i,:] += dp[i-1,:] * 2
    dp[i,:] %= mod

exc = np.sum(dp[N, (sum_a+1)//2:]) % mod
res = 3**N % mod - exc * 3

if sum_a % 2 == 0:
    dp = np.zeros((N+1, sum_a+1))
    dp[0,0] = 1
    for i in range(1, N+1):
        a_i = a[i-1]
        dp[i,a_i:] += dp[i-1,:-a_i]
        dp[i,:] += dp[i-1,:]
        dp[i,:] %= mod
    res += dp[N, sum_a//2] * 3

print(int(res % mod))
S = input()
counts = [0]
if "R" in S:
  counts.appned(1)
if "RR" in S:
  counts.append(2)
if "RRR" in S:
  counts.append(3)
print(max(counts))

### FIXED CODE ###

S = input()
counts = [0]
if "R" in S:
  counts.append(1)
if "RR" in S:
  counts.append(2)
if "RRR" in S:
  counts.append(3)
print(max(counts))
# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)


### FIXED CODE ###

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

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit


def main():
    N = int(input())
    count=0
    ans=False
    for i in range(N):
        a,b = map(int,input().split())
        if a==b:
            count += 1
        else:
            count=0
        if count >=3:
            ans=True
    print("Yes" if ans else "No")

if __name__ == '__main__':
    main()

### FIXED CODE ###


import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit


def main():
    N = int(input())
    ans=0
    for i in range(1,N+1):
        if N%i==0:
            ans+=N//i -1
        else:
            ans+=N//i
    print(ans)

if __name__ == '__main__':
    main()
import math
from functools import reduce
import sys
sys.setrecursionlimit(10**6)

def gcd_list(numbers) :
    return reduce(math.gcd, numbers)

N = int(input())
A = []
A = list(map(int, input().split()))
len = len(A)
gcd = 1

if gcd_list(A) > gcd:
    gcd = gcd_list(A)

if len > 2:
    for i in range(len):
        x = A.pop(i)
        if gcd_list(A) > gcd:
            gcd = gcd_list(A)
        A.insert(i, x)
print(gcd)


### FIXED CODE ###

import sys

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)
from collections import defaultdict
S = input()
dct = defaultdict(int)
for s in S:
  dct[s] += 1
for key, val in dct.items():
  if not val == 2:
    print('No')
    exit(1)
print('Yes')

### FIXED CODE ###

from collections import defaultdict
S = input()
dct = defaultdict(int)
for s in S:
  dct[s] += 1
for key, val in dct.items():
  if not val == 2:
    print('No')
    exit()
print('Yes')
n=int(input())
r=n**(1/2)
w=0
for i in range(1,int(r)+1):
  if n%i==0:
    w=i
x,y=w,n//w
print(x+y-1 if x=1 or y=1 else x+y-2)

### FIXED CODE ###

n=int(input())
r=n**(1/2)
w=0
for i in range(1,int(r)+1):
  if n%i==0:
    w=i
x,y=w,n//w
if x!=1 and y!=1:
  print(x+y-2)
else:
  print(max(x,y)-1)