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

import numpy as np

X, Y, Z, K = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype='int64')
b = np.array(list(map(int, input().split())), dtype='int64')
c = np.array(list(map(int, input().split())), dtype='int64')

amax = a.max()
bmax = b.max()
cmax = c.max()

a = amax - a
a.sort()
b = bmax - b
b.sort()
c = cmax - c
c.sort()


def func(o, p):
    min_ = 0
    max_ = o[-1] + p[-1]
    v = (min_ + max_) // 2
    while True:
        mat = np.searchsorted(o, v - p, side='right')
        sum_ = mat.sum()
        if sum_ > K:
            max_ = v - 1
            v = (v + min_) // 2
        elif sum_ == K:
            return v
        else:
            min_ = v + 1
            v = (v + max_ + 1) // 2


if X * Y > K:
    u = func(a, b)
    matr = np.searchsorted(a, u - b, side='right')
    d = np.array([],dtype='int64')
    for i in range(Y):
        d = np.append(d, a[:matr[i]] + b[i])
    d.sort()
else:
    d = (a + b.reshape([len(b), 1])).flatten()
    d.sort()

u = func(d, c)
matr = np.searchsorted(d, u - c, side='right')
e = np.array([],dtype='int64')
for i in range(Z):
    e = np.append(e, d[:matr[i]] + c[i])
e.sort()

t = amax + bmax + cmax
for ec in e:
    print(t - ec)

### FIXED CODE ###

import numpy as np
import sys

X, Y, Z, K = map(int, input().split())
a = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')
b = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')
c = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')

d = (a + b.reshape([len(b), 1])).flatten()
d.sort()
e = (d[-K:] + c.reshape([len(c), 1])).flatten()
e.sort()

for ec in e[-K:][::-1]:
    print(ec)
### BUGGY CODE ###

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

count=0
i=1
X=C
while (X<=B):
  X=C*i
  if(X>=A):
    if(X<=B):
      count+=1
  i+=1
  
#print(B-A-count+1)
X=D
i=1
while (X<=B):  
  X=D*i
  if(X>=A):
    if(X<=B):
    	count+=1
  i+=1
        
#print(B-A-count+1)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)

double=0
i=1
X=lcm(C, D)
while (X<=B):
  X=lcm(C, D)*i
  if(X>=A):
    if(X<=B):
    	double+=1
  i+=1
    

    
print(B-A-count+double+1)

### FIXED CODE ###

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

def gcd(a, b):
  if(a==0):
    return b  
  c = b%a  
  return gcd(c,a)

def lsm(a, b):
  return a * b // gcd(a, b)

result= B//C+B//D-B//lsm(C,D) -((A-1)//C+(A-1)//D-(A-1)//lsm(C,D))
print(B-A+1-result)
### BUGGY CODE ###

import bisect
n=int(input())
l=list(sorted(map(int,input().split())))
count=0
for i in range(1,n):
    for j in range(i+1,n):
        p=l[i]+l[j]
        count+=bisect.bisect_left(l[:i],p)-bisect.bisect_left(l[:i],l[j]-l[i]+1)
print(count)


### FIXED CODE ###

import bisect
n=int(input())
l=list(sorted(map(int,input().split())))
count=0
for i in range(1,n):
    for j in range(i+1,n):
        p=l[i]+l[j]
        count+=min(bisect.bisect_left(l,p),i)-min(bisect.bisect_left(l,l[j]-l[i]+1),i)
print(count)
### BUGGY CODE ###

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

    a = a * A[i]

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

### FIXED CODE ###

N = input()
N = int(N)
A = [int(x) for x in input().split()]
a = 1
if A.count(0) > 0:
    print(0)
    a = 0
else:
    for i in range(N):
        a = a * A[i]
        if a > 10**18:
            a = -1
            print(a)
            break

if a > 0:
    print(a)
### BUGGY CODE ###

import sys
n = int(input())
An = list(map(int, input().split()))
ans = 1
for i in range(0,n):
    ans = ans * An[i]

print(ans if ans <= 10**18 else '-1')

### FIXED CODE ###

n = int(input())
An = list(map(int, input().split()))
An.sort()
ans = 1
for i in range(0,n):
    ans = ans * An[i]
    if ans > 10**18:
        ans = -1
        break

    if An[i] == 0:
        break

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

N = int(input())
A = list(map(int, input().split()))
res = 1
for a in A:
  res *= a
if res > 1e18:
  print(-1)
else:
  print(res)

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
A.sort()
res = 1
for a in A:
  res *= a
  if res > 1e18:
    print(-1)
    sys.exit()
print(res)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    r = bisect(x, x[i]+2*D)
    for j in range(i+1, r):
      if j>N-1:break
      h[j] = h[j]-h_int*A

print(int(cnt))


### FIXED CODE ###

#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
damage=[0]*(N+1)

for i in range(len(x)):
    damage[i] += damage[i-1]
    h[i] -= damage[i]
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    damage[i]+=h_int*A
    r=bisect(x,x[i]+2*D)
    #print(damage[i])
    damage[r]-= A*h_int
    

print(int(cnt))
### BUGGY CODE ###

from sys import stdin
N,M=[int(x) for x in stdin.readline().rstrip().split()]
A=[int(x) for x in stdin.readline().rstrip().split()]
data=[]
A = sorted(A)
for i in range(M):
    r,q=[int(x) for x in stdin.readline().rstrip().split()]
    if q >= A[0]:
        for j in range(r):
            A.append(q)
 
ans = sum(sorted(A)[::-1][:N])
print(ans)

### FIXED CODE ###

from sys import stdin
N,M=[int(x) for x in stdin.readline().rstrip().split()]
A=[(int(x),1) for x in stdin.readline().rstrip().split()]
data=[]
for i in range(M):
    r,q=[int(x) for x in stdin.readline().rstrip().split()]
    A.append((q,r))
ans=0
cnt=0
for j in reversed(sorted(A)):
    cnt+=j[1]
    ans+=(j[0]*j[1])
    if cnt > N:
        ans = ans-(j[0]*(cnt-N))
        break
print(ans)
### BUGGY CODE ###

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

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

for i in range(min(n,len(d))):
    if a[i]<d[i]: a[i]=d[i]

print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a = list(map(int, input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
#print(bc)
bc=sorted(bc,key= lambda x:x[1],reverse=True)
#print(bc)

bc2=[]
for i in range(m):
    bc2.extend([bc[i][1]]*bc[i][0])
    if len(bc2)>n: break
#print(bc2)
a.extend(bc2)
a.sort(reverse=True)

print(sum(a[:n]))
### BUGGY CODE ###

R, G, B, N = list(map(int, input().split()))
ret = 0
for r in range(N//R+1):
    for g in range((N-r)//G+1):
        if N - (R*r+G*g) >= 0:
            if (N - (R*r+G*g)) % B == 0:
                ret += 1
print(ret)

### FIXED CODE ###

R, G, B, N = list(map(int, input().split()))
R, G, B = sorted([R, G, B], reverse=True)
ret = 0
for r in range(N//R+1):
    if G == 1:
        ret += N-r+1
    else:
        for g in range((N-r)//G+1):
            if N - (R*r+G*g) >= 0:
                if (N - (R*r+G*g)) % B == 0:
                    ret += 1
print(ret)
### BUGGY CODE ###

N = int(input())
ss = [input() for i in range(N)]
setss = set(ss)
maxes = [0]*len(setss)
listsetss = list(setss)
for i in range(len(setss)):
  maxes[i] = ss.count(listsetss[i])
mostPoll = max(maxes)
winners = []
for i in range(len(maxes)):
  if maxes[i] == mostPoll:
    winners.append(listsetss[i])
winners.sort()

for s in winners:
  print(s)

### FIXED CODE ###

n = int(input())
d = {}
for _ in range(n) :
    s = input()
    if s in d :
        d[s] += 1
    else :
        d[s] = 1

mx = max(d.values())
for s in sorted(k for k in d if d[k] == mx) :
    print(s)
### BUGGY CODE ###

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))
C.sort()

def next_max(mi,v):
    l, r = 0, mi-1
    while l <= r:
        mid = int((l+r)/2)
        if C[mid] == v: return mid - 1
        if C[mid] > v:
            r = mid - 1
        else:
            l = mid + 1
    return r

for i in range(Q):
    t = int(input())
    idx = N-1
    m = C[-1]% t
    idx = next_max(idx,C[idx]-m)
    while idx >= 0:
        amr = C[idx]%t
        m = max(m,amr) 
        idx = next_max(idx,C[idx]-amr)
    print(m)

### FIXED CODE ###

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))

M = max(C)+1
t1 = [0]*(M)
for v in C:
    t1[v] = 1

t2 = [0]*(M)
v = 0
for i in range(M):
    if t1[i]:
        v = i
    t2[i] = v

for i in range(Q):
    t = int(input())
    n_v = M-1
    m = 0
    while n_v != 0:
        amr = n_v % t
        m = max(m, amr) 
        tmp = n_v-m-1
        if tmp <= 0: break
        n_v = t2[tmp]

    print(m)
### BUGGY CODE ###

N = int(input())
c = input()

x =[0] * N

for i, cc in enumerate(c):
    if cc == "R":
        x[i] = 1

#一番左が赤だと削れる
#一番右が白だと削れる
cmd = 0
while len(x) > 0:
    while len(x) > 0 and x[0] == 1:
        x.pop(0)
    while len(x) > 0 and x[-1] == 0:
        x.pop(-1)
    while len(x) > 0 and x[0] == 0 and x[-1] == 1:
        x[0] = 1
        x[-1] = 0
        cmd += 1

print(cmd)







### FIXED CODE ###

N = int(input())
c = input()

x =[0] * N

ww = 0
rr = 0
for i, cc in enumerate(c):
    if cc == "R":
        x[i] = 1
        rr += 1
    else:
        ww += 1

cmd = 0
for i in range(rr):
    if x[i] == 0:
        cmd += 1

cmd2 = 0
for j in range(rr+1, len(x)):
    if x[j] == 1:
        cmd2 += 1


print(max(cmd, cmd2))
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
p=[]
for i in range(n):   
 p.append(i1())

s=0
while p[0]!=1 or p[-1]!=n:
 j=0
 if p[0]==1 and p[-1]!=n:
   k=p[-1]
   s+=n-p[-1]
   while len(p)>j:
       if p[j]>k:
         p.pop(j)
         j-=1
       j+=1
   p=p+list(range(k+1,n+1))
 if p[0]!=1 and  p[-1]==n:
   k=p[0]
   s+=p[0]-1
   while len(p)>j:
       if p[j]<k:
          p.pop(j)
          j-=1
       j+=1
   p=list(range(1,k))+p
 if p[0]!=1 and  p[-1]!=n:

  if n-p[-1]>p[0]-1:
   k=p[0]
   s+=p[0]-1
   while len(p)>j:
       if p[j]<k:
          p.pop(j)
          j-=1
       j+=1
   p=list(range(1,k))+p
  else:
   k=p[-1]
   s+=n-p[-1]
   while len(p)>j:
       if p[j]>k:
         p.pop(j)
         j-=1
       j+=1
   p=p+list(range(k+1,n+1))
j=0

while n-1>j:
   if p[j]>p[j+1]:
     s+=1
     if p[j+1]-1<n-p[j]:
        p.insert(0,p[j+1])
        p.pop(j+2)
        j+=1
     else:
        p.append(p[j])
        p.pop(j)
   else:
        j+=1
print(s)

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
p=[]
q=[0 for i in range(n)]
for i in range(n):   
 p.append(i1())
 q[p[-1]-1]=i
k=1
s=0
for i in range(n-1):
  if q[i+1]-q[i]>0:
     k+=1
  else:
     s=max(s,k)
     k=1
s=max(s,k)
print(n-s)
### BUGGY CODE ###

# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

n = int(sys.stdin.readline().rstrip())
v_s = list(map(int, sys.stdin.readline().rstrip().split()))

eval_type = {}
odd_type = {}

# v を eo_type(dict) に追加する
def add_v(eo_type, v):
  if v not in eo_type:
    eo_type[v] = 1
  else:
    eo_type[v] += 1

# eo_type(dict) の max value 2つの index を返す
def get_max2(eo_type):
  mx1, mx2 = [0] * 2
  for i in eo_type:
    if (mx1 not in eo_type) or (eo_type[mx1] < eo_type[i]):
      mx2 = mx1
      mx1 = i
    elif (mx2 not in eo_type) or (eo_type[mx2] < eo_type[i]):
      mx2 = i
  return([mx1, mx2])


def solve(idx_e, idx_o):
  if idx_e == 0 or idx_o == 0:
    return(sys.maxsize)
  elif idx_e == idx_o:
    return(min(n-eval_type[idx_e], n-odd_type[idx_o]))
  else:
    return(n - eval_type[idx_e] - odd_type[idx_o])


if __name__ == "__main__":
  for i in range(len(v_s)):
    if i % 2 == 0:
      add_v(eval_type, v_s[i])
    else:
      add_v(odd_type, v_s[i])
  
    ve1,ve2 = get_max2(eval_type)
    vo1,vo2 = get_max2(odd_type)
  
  print(min(solve(ve1,vo1), solve(ve1,vo2), solve(ve2,vo1)))
  

### FIXED CODE ###

# /user/bin/python
# -*- coding: utf-8 -*-
from collections import Counter
import sys

n = int(sys.stdin.readline().rstrip())
v_s = list(map(int, sys.stdin.readline().rstrip().split()))

v_even = Counter(v_s[0::2]).most_common()
v_even.append((0,0))
v_odd = Counter(v_s[1::2]).most_common()
v_odd.append((0,0))

if v_even[0][0] != v_odd[0][0]:
  print(n-v_even[0][1]-v_odd[0][1])
else:
  print(min(n-v_even[0][1]-v_odd[1][1], n-v_odd[0][1]-v_even[1][1]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = []
for i in range(n):
    s.append(sum(a[0:i+1]))

count = 0
ans1 = 0
for i in range(n):
    if i%2 == 0:
        if s[i]+count > 0:
            continue
        else:
            ans1 += 1-(s[i]+count)
            count += 1-(s[i]+count)
    else:
        if s[i]+count < 0:
            continue
        else:
            ans1 += (s[i]+count) + 1
            count -= (s[i]+count) + 1
            
count1 = 0
ans2 = 0
for i in range(n):
    if i%2 == 1:
        if s[i]+count1 > 0:
            continue
        else:
            ans2 += 1-(s[i]+count1)
            count1 += 1-(s[i]+count1)
    else:
        if s[i]+count1 < 0:
            continue
        else:
            ans2 += (s[i]+count1) + 1
            count1 -= (s[i]+count1) + 1
            
print(min(ans1,ans2))
            

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = []
for i in range(n):
    if i == 0:
        s.append(a[0])
    else:
        s.append(a[i]+s[-1])

count = 0
ans1 = 0
for i in range(n):
    if i%2 == 0:
        if s[i]+count > 0:
            continue
        else:
            ans1 += 1-(s[i]+count)
            count += 1-(s[i]+count)
    else:
        if s[i]+count < 0:
            continue
        else:
            ans1 += (s[i]+count) + 1
            count -= (s[i]+count) + 1
            
count1 = 0
ans2 = 0
for i in range(n):
    if i%2 == 1:
        if s[i]+count1 > 0:
            continue
        else:
            ans2 += 1-(s[i]+count1)
            count1 += 1-(s[i]+count1)
    else:
        if s[i]+count1 < 0:
            continue
        else:
            ans2 += (s[i]+count1) + 1
            count1 -= (s[i]+count1) + 1
            
print(min(ans1,ans2))
### BUGGY CODE ###

#from fractions import Fraction
from math import ceil
from heapq import heappush, heappop

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

A_queue = []
for a in input().split():
	a = float(a)
	heappush(A_queue, (-a, a, 1))

def calc(K):
	while K > 0:
		length, a, div = heappop(A_queue)
		div += 1
		K -= 1
		heappush(A_queue, (-a / div, a, div))
	return -A_queue[0][0]

print(ceil(calc(K)))


### FIXED CODE ###

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

A_list = list(map(int, input().split()))

# search smallest i such that f(i) == True
def auto_bisearch_smallest(f, s = None):
	if s == None:
		s = 0
		w = -1
		while f(s) == True:
			s = w
			w *= 2
	e = s
	w = 1
	while f(e) == False:
		e = s + w
		w *= 2
	
	return bisearch_smallest(f, s, e + 1)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

def calc(length):
	count = 0
	for a in A_list:
		if a > length:
			if a % length == 0:
				count += (a // length) - 1
			else:
				count += a // length
	return count

print(auto_bisearch_smallest(lambda length: calc(length) <= K, 1))
### BUGGY CODE ###

import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a



nu=int(input())
total=0
for p in range(1,nu):
    s=collections.Counter(prime_factorize(p))
    sama=1
    for j in s.values():
        sama=sama*(j+1)
    total+=sama
print(total)

### FIXED CODE ###

import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a



nu=int(input())
total=0
for p in range(1,nu):
    s=collections.Counter(prime_factorize(p))
    sama=1
    for j in s.values():
        sama=sama*(j+1)
    total+=sama
print(total)
### BUGGY CODE ###

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[input() for _ in range(H)]
# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
S = ['##{}##'.format(row) for row in S]
S.insert(0, '##{}##'.format('#' * W))
S.insert(0, '##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))


MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

cost0 = deque()

cost0.append((CH+1,CW+1,0))
Cost[CH+1][CW+1] = 0;

# used = set()
walk=[(1,0),(0,1),(-1,0),(0,-1)]
warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
# print(warp)

cost1 = deque()

while 0 < len(cost0):
	h,w,c=cost0.popleft()
	cost1.append((h,w,c))

	for i,j in walk:
		if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
			Cost[h+i][w+j] = c
			# print("updl ", i,j,h+i,w+j,c)
			cost0.appendleft((h+i,w+j,Cost[h+i][w+j]))

	if len(cost0) == 0:

		while 0 < len(cost1):
			h,w,c=cost1.popleft()
			# print(h,w,c)
			for i,j in warp:
				# print(i,j)
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						cost0.append((h+i,w+j,Cost[h+i][w+j]))


if Cost[DH+1][DW+1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH+1][DW+1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    point[p] += x
def dfs(now,last ,add):
    point[now] += add
    for next in ki[now]:
        if next == last:continue
        dfs(next,now,point[now])
dfs(0,-1,0)
print(*point)

### 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)]

ki = [[]for _ in range(N)]
for a,b in AB:
    a-=1
    b-=1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*(N)
for p,x in PX:
    p-=1
    point[p]+=x
def dfs(now, last ,add):
    point[now]+= add
    for x in ki[now]:
        if (x == last):continue
        dfs(x,now,point[now])
dfs(0,0,0)
print(*point)
### BUGGY CODE ###

import math

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

#maxresult = [(a * x * 1.0 // b) - a * (x * 1.0 // b) for x in range(n+1) if (a * x * 1.0 // b) - a * (x * 1.0 // b) >= maxresult]

maxresult = 0

for x in range(n+1):
    if (a * x * 1.0 // b) - a * (x * 1.0 // b) >= maxresult:
        maxresult = int((a * x * 1.0 // b) - a * (x * 1.0 // b))

print(maxresult)

### FIXED CODE ###

import math

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

maxresult = 0

#これはタイムオーバー
#for x in range(n+1):
#    if (a * x * 1.0 // b) - a * (x * 1.0 // b) >= maxresult:
#        maxresult = (a * x * 1.0 // b) - a * (x * 1.0 // b)

#これもタイムオーバー
#for x in range(n+1):
#    if a * math.modf(x*1.0/b)[0] >= maxresult:
#        maxresult = a * math.modf(x*1.0/b)[0]

"""
解説動画を見て、再考
x = pB + qと変形する。（https://twitter.com/chokudai/status/1256806061194874881）
floor[Ax / B]
=floor[(APB+Aq) / B]
=Ap + floor[Aq / B]

A * floor[x / B]
= A * floor[(pB+q) / B]
= A * (p + floor[q/B])

よって、
floor[Ax / B] - A * floor[x / B]
=Ap + floor[Aq / B] - Ap - A * floor[q / B]
=floor[Aq / B] - A * floor[q / B]
  #x = pB + qであるため、floor[q/B] = 0
=floor[Aq / B]
  #q = (x % B)なので
=floor[A/B * (x % B)]
この値が最大になればよく、xは整数なので、
x = B-1の時が最大となる。

ただしN < B-1の場合は、x = B-1を取れないので、
そのときにはxの最大値x=Nとなる。
"""

if n < b-1:
    x = n
else:
    x = b-1
maxresult = a * (x%b) // b

print(int(maxresult))
### BUGGY CODE ###

s = str(input())
K = int(input())
stack = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        sub = s[i:j]
        if sub not in stack:
            stack.append(sub)
stack.sort()
print(stack[K-1])

### FIXED CODE ###

s = str(input())
K = int(input())
stack = []
for i in range(len(s)):
    for j in range(i+1, min(i+K, len(s))+1):
        sub = s[i:j]
        if sub not in stack:
            stack.append(sub)
stack.sort()
print(stack[K-1])