Harryxun/stf_run huggingface dataset:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 6
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 10
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)
n_dice, n_choice = map(int, input().split())
dice_list = tuple(map(int, input().split()))
sumofarea_list = [sum(dice_list[i:i+n_choice]) for i in range(n_dice - n_choice + 1)]
print(max(sumofarea_list)/2 + n_choice / 2)

### FIXED CODE ###

list_len = int(input())
integer_list = input().split()
if list_len == len(set(integer_list)):
    print('YES')
else:
    print('NO')
N = int(input())
ana = {}
answer = 0

for i in range(N):
    s = sorted(input())
    new_str = ''.join(s)
    flag = 0

    try:
        k = ana.keys().index(new_str)y
        ana[k] += 1
        answer += ana[k]

    except:
        ana[new_str] = 0

print(answer)

### FIXED CODE ###

N = int(input())
ana = {}
answer = 0

for i in range(N):
    s = sorted(input())
    new_str = ''.join(s)
    flag = 0

    if new_str in ana.keys():
        ana[new_str] += 1
        answer += ana[new_str]
        flag = 1

    if flag == 0:
        ana[new_str] = 0

print(answer)
N = int(input())
arr =  [int(i) for i in input().split()] 

count = 0
while(True):
    for i in range(N):
        if arr[i] % 2 == 0:
            arr[i] = arr[i] / 2
            if i == 2:
                count += 1
        else:
            break
    else:
        continue
    break
        
        



### FIXED CODE ###


a = input()

count = 0
for i in a:
    if i == '1':
        count += 1
print(count)
q=input()
x=[int(i) for i in input().split()]
cnt=input()
y=[int(i) for i in input().split()]

if max(x) >= max(y):
    MAX=max(x)
else:
    MAX=max(y)
z=[0]*1000000000

print('YES')

### FIXED CODE ###


q=input()
x=[int(i) for i in input().split()]
cnt=input()
y=[int(i) for i in input().split()]

if max(x) >= max(y):
    MAX=max(x)
else:
    MAX=max(y)

dic = {}

for k in x :
    if k in dic.keys() :
        dic[k] += 1
    else :
        dic[k] = 1
    
for i in y :
    if i in dic.keys() :
        dic[i] -= 1
        if dic[i] == -1 :
            print('NO')
            exit()
    else :
        print('NO')
        exit()
print('YES')
n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
if n == 1:
    for i in range(10):
        tmp = str(i)
        flag = True
    for j in range(m):
        if tmp[arr[j][0]-1] != str(arr[j][1]):
            flag = False
    if flag:
        print(i)
        break
    else:
        print(-1)
else:
    for i in range(10**(n-1),10**n):
        tmp = str(i)
        flag = True
    for j in range(m):
        if tmp[arr[j][0]-1] != str(arr[j][1]):
            flag = False
    if flag:
        print(i)
        break
    else:
        print(-1)

### FIXED CODE ###

n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
if n == 1:
    for i in range(10):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
else:
    for i in range(10**(n-1),10**n):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
data = input().split()
a=int(data[0])
b=int(data[1])
if a == b:
	print("a == b")
elif a > b:
	print("a > b")
else
	print("a < b")
	

### FIXED CODE ###

data = input().split()
a=int(data[0])
b=int(data[1])
if a == b:
	print("a == b")
elif a > b:
	print("a > b")
else:
	print("a < b")
bilding = [[[0 for i in range(10)] for j in range(3)]for k in range(4)]

n = int(input())
i = 0
while i < n:
    b, f, r, v = map(int, raw_input().split())

### FIXED CODE ###

bilding = [[[0 for x in range(10)] for x in range(3)]for x in range(4)] 
n = int(input())
for k in range(n):
    b, f, r, v = map(int, raw_input().split())
    bilding[b-1][f-1][r-1] += v

for b in range(4):
    for f in range(3):
        print(" "+" ".join(map(str, bilding[b][f])))
    if b != 3:
        print("#"*20)
a=input()
b=input()
mennseki=a*b
syuu=(a+b)*2
print mennseki,syuu

### FIXED CODE ###

a,b=map(int,raw_input().split())
mennseki=a*b
syuu=(a+b)*2
print mennseki,syuu
import math
K = int(input())
m = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      m += gcd(i, j, k)
print(m)

### FIXED CODE ###

from math import gcd
K = int(input())
m = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    w = gcd(i, j)
    if w==1:
      m += K
    else:
      for k in range(1, K+1):
        m += gcd(w, k)
print(m)
n,m=[int(x) for x in input().rstrip().split()]
a=[int(input()) for i in range(m)]
oks=[True for i in range(n+1)]

mod=10**9+7
dp=[0 for i in range(n+1)]
for i in a:
  oks[i]=False

if oks[1]==True:
  dp[1]=1
if oks[2]==True:
  dp[2]=dp[1]+1

for i in range(3,n+1):
  if oks[i]==True:
    dp[i]=dp[i-2]+dp[i-1]
print(dp[n]%mod)

### FIXED CODE ###

n,m=[int(x) for x in input().rstrip().split()]
a=[int(input()) for i in range(m)]
oks=[True for i in range(n+1)]

mod=10**9+7
dp=[0 for i in range(n+1)]
for i in a:
  oks[i]=False

if oks[1]==True:
  dp[1]=1
dp[0]=1
for i in range(2,n+1):
  if oks[i]==True:
    dp[i]=dp[i-2]+dp[i-1]
print(dp[n]%mod)
import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.zeros(N,dtype=int)
for i in range(1, N):
    s=max(0, i-k)
    dp[i] = min(dp[s:i]+abs(h[s:i]-h[i])
print(dp[-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.zeros(N,dtype=int)
for i in range(1, N):
    s=max(0, i-K)
    dp[i] = min(dp[s:i]+abs(h[s:i]-h[i]))
print(dp[-1])
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
s = [a,b,c,d,e]
kk = "Yay!"
for z in range(lan(s)):
  ss = s[(z+1):]
  for y in ss:
    if s[z] - y > k :
      kk=":("
      
print(kk)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if (e-a)> k:
  print(":(")
else:
  print("Yay!")
N,M = map(int, input().split(" "))
XList = list(map(int,input().split()))

XList = sorted(XList)
deltaList = []

for i in range(M-1) :
    deltaList.append(XList[i+1] - XList[i])
deltaList = sorted(deltaList, reverse=True)

for i in range(N-1) :
    deltaList[i] = 0
print(sum(deltaList))

### FIXED CODE ###

N,M = map(int, input().split(" "))
XList = list(map(int,input().split()))

XList = sorted(XList)
deltaList = [0]

for i in range(M-1) :
    deltaList.append(XList[i+1] - XList[i])
deltaList = sorted(deltaList, reverse=True)


for i in range(N-1) :
    deltaList[i] = 0
    if i == len(deltaList)-1 :
        break
print(sum(deltaList))
from math import sqrt, isclose
a, b, c = [int(i) for i in input().split()]
d = sqrt(c) - sqrt(a) - sqrt(b)
if isclose(d,0) or d<0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

a, b, c = [int(i) for i in input().split()]
if a + b >= c:
    print("No")
else:
    if 4 * a * b < (c - a - b)** 2:
        print("Yes")
    else:
        print("No")
from math import gcd
a,b = map(int, input().split())
print((a*b)//gcd(a,b))

### FIXED CODE ###

from fractions import gcd
a,b = map(int, input().split())
print((a*b)//gcd(a,b))
N=int(input())
 
print(int(N*(N-1)//2))

### FIXED CODE ###

s = input()
t = input()
ans = 0
for i in range(len(s)):
    if s[i] == t[i]:
        ans+=1
        
print(ans)
n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(A):
  A[i]=(1+A[i])/2
sum=0
for i in range(0,n-k+1):
  sum=max(sum,sum(A[i:i+k+1]))
print(sum)

### FIXED CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
  A[i]=(1+A[i])/2
S=[0 for i in range(n+1)]
for i in range(n):
  S[i+1]=S[i]+A[i]
ans=0
for i in range(n-k+1):
  ans=max(ans,S[i+k]-S[i])
  
print(ans)
x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
　　print(com[a])


### FIXED CODE ###

x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
  exit()
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
print(com[-1])
for sys import stdin
N=int(stdin.readline().rstrip())
T,A=[int(x) for x in stdin.readline().rstrip().split()]
elev=[int(x) for x in stdin.readline().rstrip().split()]
cnt=0
comp=10000
for i in elev:
    cnt+=1
    temperature=T-(i*0.006)
    tmp=abs(A-temperature)
    if comp > tmp:
        comp=tmp
        ans=cnt
print(ans)

### FIXED CODE ###

from sys import stdin
N=int(stdin.readline().rstrip())
T,A=[int(x) for x in stdin.readline().rstrip().split()]
elev=[int(x) for x in stdin.readline().rstrip().split()]
cnt=0
comp=10000
for i in elev:
    cnt+=1
    temperature=T-(i*0.006)
    tmp=abs(A-temperature)
    if comp > tmp:
        comp=tmp
        ans=cnt
print(ans)
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
p=[0]
a=1
k=0
f=0
if n==0:
  print(p(0))
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  print(l[0])
else:
  print(-1)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
  if a<=0 and i!=len(g)-1:
    f+=1
    break
  if a<0 and i==len(g)-1:
    f+=1
    break
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)
import sys as chokudairedcoderatcoderowner
A,B,C = map(int,chokudairedcoderatcoderowner.stdin.readline())

if A == B:
  print(C)
else if A == C:
  print(B)
else:
  print(A)

### FIXED CODE ###

import sys as cghavcjhcbejwcbbsmbcjsdbcjdcadhbcjbdsjjcdjabjadbjsbcjdsbcsbcnsbcdnbcmbcmdabcdbjwhckfmknvskndleccdajbubcrjhebuoqbjhbjcdnaaayruegfubefruebhvy38bjhbvvbhcba
A,B,C = map(int,cghavcjhcbejwcbbsmbcjsdbcjdcadhbcjbdsjjcdjabjadbjsbcjdsbcsbcnsbcdnbcmbcmdabcdbjwhckfmknvskndleccdajbubcrjhebuoqbjhbjcdnaaayruegfubefruebhvy38bjhbvvbhcba.stdin.readline().split())

if A == B:
  print(C)
elif A == C:
  print(B)
else:
  print(A)
N=int(input())
x=N*800
y=N//15*200
print(eval(x-y))

### FIXED CODE ###

N=int(input())
x=int(N*800)
y=int(N//15*200)
print(x-y)
list = []
indent = 0
for i in range(5):
  memory = 9
  list.append(int(input()))
  if memory > list[i] % 10 && list[i] % 10 != 0:
  	indent = i
 
count = 0
for i in range(5):
  if i == indent:
    count += list[i]
  else:
    count += 10 * (int(list[i]/10) + 1)
 
print(count)

### FIXED CODE ###

list = []
for i in range(5):
	list.append(int(input()))
k = int(input())

for i in range(5):
  for j in range(4-i):
    if list[i+1+j] - list[i] > k:
      print(":(")
      break
  else:
    print("Yay!")
  break
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
from bisect import bisect_left, bisect_right, insort
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def MS(): return map(str,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
#N = I()
#A = [LI() for _ in range(N)]

n,k = MI()
a = LI()
ans = [1] * n
memo = [-1] * n
memo[0] = 0
s = 0
for i in range(1,n):
    if memo[a[ans[i-1]-1]-1] == -1:
        ans[i] = a[ans[i-1]-1]
        s += 1
        memo[ans[i] - 1] = s

    else:
        t = memo[a[ans[i-1]-1]-1]
        break
if k <= t:
    print(ans.index(k) + 1)
elif t == 0:
    print(ans[(k - 1) % (s-t +1) +1])
else:
    print(ans[(k-(t-1)-1) % (s-t+1) + t])

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
from bisect import bisect_left, bisect_right, insort
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def MS(): return map(str,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
#N = I()
#A = [LI() for _ in range(N)]

n,k = MI()
a = LI()
ans = [1] * n
memo = [-1] * n
memo[0] = 0
s = 0
for i in range(1,n):
    if memo[a[ans[i-1]-1]-1] == -1:
        ans[i] = a[ans[i-1]-1]
        s += 1
        memo[ans[i] - 1] = s

    else:
        t = memo[a[ans[i-1]-1]-1]
        break
if k <= t:
    print(ans[k])
elif t == 0:
    print(ans[(k - 1) % (s-t +1) +1])
else:
    print(ans[(k-(t-1)-1) % (s-t+1) + t])
from collections import deque
S = input()
x, y = map(int, input().split(' '))

move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
direction = 0

position = set((0, 0))
state = [((0, 0), 0)]

can_move = False
idx = 0

for s in S:
    next_position = set()
    next_state = []
    for p, d in state:
        if s == 'T':
            next_position.add(p)
            next_state.append((p, d + 1))
            next_state.append((p, d - 1))
        else:
            xx, yy = p
            mxx, myy = move[d]
            np = (xx + mxx, yy + myy)
            next_position.add(np)
            next_state.append((np, d))
    position = next_position
    state = next_state

if (x, y) in position:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = input()
x, y = map(int, input().split(' '))

F = [len(s) for s in S.split('T')]

memo_x = [set((F[0], ))]
memo_y = [set((0, ))]

for i, f in enumerate(F[2::2]):
    next_memo_x = set()
    for prev_x in memo_x[i]:
        next_memo_x.add(prev_x + f)
        next_memo_x.add(prev_x - f)
    memo_x.append(next_memo_x)

for i, f in enumerate(F[1::2]):
    next_memo_y = set()
    for prev_y in memo_y[i]:
        next_memo_y.add(prev_y + f)
        next_memo_y.add(prev_y - f)
    memo_y.append(next_memo_y)

if x in memo_x[-1] and y in memo_y[-1]:
    print('Yes')
else:
    print('No')
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    # AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


if __name__ == '__main__':
    main()
N = int(input())
V = list(map(int,input().split()))
ans=0
V.sort()
S=V[0]
for i in N-1:
  ans += (S + V[i])/2
  S=V[i]
print(ans)  


### FIXED CODE ###

N = int(input())
V = list(map(int,input().split()))
V.sort()
S = V[0]
for i in range(N):
  S = (S + V[i])/2
print(S)
K = int(input())
list = [1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]
print(list[K+1])

### FIXED CODE ###

K = int(input())
list = [1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]
print(list[K-1])
N = input()
K = int(input())
ans = '1'
for i in range(K):
  if i >= len(N):
    break
  if N[i] != '1':
    ans = N[i]
  	break
print(ans)
  

### FIXED CODE ###

N = input()
K = int(input())
ans = '1'
for i in range(K):
  if i >= len(N):
    break
  if N[i] != '1':
    ans = N[i]
    break
print(ans)
Q = int(input())
lr = [tuple(map(int, input().split())) for i in range(Q)]


def primes(n):
    ret = []
    A = [i for i in range(2, n+1)]
    k = 0
    s = n**0.5
    while(k < s):
        ret.append(A[0])
        k = A[0]
        A = [x for x in A if x % k]
    ret += A
    return ret


prime = primes(10**5)

table = collections.defaultdict(int)
prime_s = set(prime)
t = [0]*(10**5 + 1)
for i in range(1, 10**5+1):
    if i in prime_s and (i+1)//2 in prime_s:
        t[i] = 1
for i in range(1, 10**5+1):
    t[i] = t[i] + t[i-1]

for l, r in lr:
    print(t[r] - t[l-1])


### FIXED CODE ###

import math
Q = int(input())

def sosuu(x):
  if x == 1:
    return False
  else:
    for i in range(1,int(math.sqrt(x))):
      if x % (i+1) == 0:
        return False
    return True

table=[0]*50001
for i in range(1,50001):
  if sosuu(2*i - 1) and sosuu(i):
    table[i]=table[i-1] + 1
  else:
    table[i]=table[i-1]
    
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  ans[i]=table[(r+1)//2] - table[(l+1)//2 - 1]
  
for i in range(Q):
  print(ans[i])
N,M=map(int,input().split())
s=[0]*M
c=[0]*M
for i in range(0,M):
  s[i],c[i]=map(int,input().split())
  
flag=0
data=[-1 for i in range(0,N)]
for i in range(0,M):
  if data[s[i]-1]==-1:
    data[s[i]-1]=c[i]
  else:
    if data[s[i]-1]!=c[i]:
      flag=1
if data[0]==0:
  flag=1
if flag==1:
  print(-1)
else:
  for i in range(0,M):
    if data[i]==-1:
      if i==0:
        data[i]=1
      else:
        data[i]=0
  ans=''
  for i in range(0,M):
    ans+=str(data[i])
  print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
s=[0]*M
c=[0]*M
for i in range(0,M):
  s[i],c[i]=map(int,input().split())

flag=0
data=[-1 for i in range(0,N)]
for i in range(0,M):
  if data[s[i]-1]==-1:
    data[s[i]-1]=c[i]
  else:
    if data[s[i]-1]!=c[i]:
      flag=1
if data[0]==0 and N!=1:
  flag=1
if flag==1:
  print(-1)
else:
  for i in range(0,N):
    if data[i]==-1:
      if i==0 and N>1:
        data[i]=1
      else:
        data[i]=0
  ans=''
  for i in range(0,N):
    ans+=str(data[i])
  print(ans)
a, b, c = map(int, input().split())
divisores = []
for i in range(min(a,b), 1, -1):
    if len(divisores) == c:
        break
    if a % i == 0 and b % i == 0:
        divisores.append(i)
print(divisores[c-1])

### FIXED CODE ###

li=[int(i) for i in input().split()]
a=li[0]
b=li[1]
k=li[2]
c=[]
for i in range(1,min(a,b)+1):
    if(a%i==0 and b%i==0):
        c+=[i]

print(c[-k])
N, Q = map(int, input().split())
tree = [[] for _ in range(N)]

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

X = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x

ans = [0]*N

def dfs(u, parent=None):
    ans[u] = ans[parent] + X[u]
    for v in tree[u]:
        if v != parent:
            dfs(v, u)

dfs(0, 0)
print(' '.join([str(i) for i in ans]))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
 
def main():
    n, q = map(int, input().split())
    node = [[]for _ in range(n)]
    looked = [1] * n
    for i in range(n - 1):
        a, b = map(int, input().split())
        node[b - 1].append(a - 1)
        node[a - 1].append(b - 1)
    counter = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        counter[p - 1] += x
    queue = deque([0])
    looked[0] = 0
    while queue:
        now = queue.pop()
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
 
main()