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

INF = 10**2 - 1 #無限大
SMAX = 3000 + 1

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、一致文字列長を二次軸に取り
その値として：s2の使用済文字数の最小値を入れる
　　　　　　　0列は 0 それ以外がINFで初期化
'''
dp = [[INF] * (len(s1)+1) for i in range(len(s1)+1)]
for i in range(0,len(s1)+1):
    dp[i][0] = 0
#print(dp[0])

for s1pos in range(1,len(s1)+1):
    s = s1[s1pos-1:s1pos]
    #print("s=",s,"--------")
    for psLen in range(1,s1pos+1):
        s2pos = dp[s1pos-1][psLen-1] + 1
        spos = s2[s2pos-1:].find(s)
        dp[s1pos][psLen] = dp[s1pos-1][psLen]
        if spos == -1:
            pass
        else:
            if dp[s1pos][psLen] > s2pos+spos:
                dp[s1pos][psLen] = s2pos+spos
        #print("s=",s,"ps2=",s2[s2pos-1:],"spos=",spos,"s1pos=",s1pos,"s2pos=",s2pos,"dp=",dp[s1pos])

#答えは、DP配列を最善値を出したところを逆方向に辿る
Ans = ""
pos1 = len(s1)
pos2 = len(s1)
for s1pos in range(pos1,0,-1):
    s = s1[s1pos-1:s1pos]
    for psLen in range(pos2,0,-1):
        if dp[s1pos][psLen] < INF:
            if dp[s1pos-1][psLen] > dp[s1pos][psLen]:
                Ans = s + Ans
                pos2 = psLen - 1
                break
            else:
                continue
    #print("s1pos=",s1pos,"s=",s,"dp=",dp[s1pos],"Ans=",Ans)

print(Ans)


### FIXED CODE ###

INF = 10**10 - 1 #無限大
SMAX = 3000 + 10

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (SMAX) for i in range(SMAX)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)
### BUGGY CODE ###

from collections import deque

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

A = [[] for i in range(N)]

for i in range(M) :
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])

dist = [False for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg :
        break
    
    if dist[i] :
        continue
    
    dist[i] = 0
    
    q = deque([i])
    
    while q :
        now = q.pop()
        for to,d in A[now] :
            if not dist[to] :
                dist[to] = dist[now] + d
                q.append(to)
            
            elif dist[to] == dist[now] + d :
                continue
            
            else :
                ans = "No"
                flg = 1
                q = deque()
                break

print(ans)


### FIXED CODE ###

N,M = map(int,input().split())
A = [[] for i in range(N+1)]

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])

distance = ["#" for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg == 1 :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        v = stack.pop()
        
        for to,d in A[v] :
            if distance[to] == "#" :
                distance[to] = distance[v] + d
                stack.append(to)
            
            elif distance[to] != distance[v] + d :
                ans = "No"
                stack = []
                flg = 1
                break
                

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

s = input()
k = int(input())
 
s = list(s)
v = 5 * 10**15
a = []
for i in range(9):
  a.append(i ** v)

nuar = []
lear = []
co = 0
rear = 0

for i in s:
  for j in range(1,10):
    if int(i) == j:
      nuar.append(j)
      rear += a[j - 1]
      lear.append(rear)
      
for p in range(len(s)):
  if p == 0:
    if lear[p] >= k:
      print(nuar[p])
  elif lear[p] >= k and lear[p - 1] < k:
    print(nuar[p])
  
 

### FIXED CODE ###

s = input()
k = int(input())
 
s = list(s)

co = 1
      
for i in s:
  if int(i) == 1:
    if co == k:
      print(int(i))
      break
  else:
    print(int(i))
    break
  co += 1
### BUGGY CODE ###

a = []
while True:
    inp = input().split()
    if inp[0] == "insert":
        a.append(int(inp[1]))
    elif inp[0] == "extract":
        a.sort()
        print(a.pop())
    else:
        break

### FIXED CODE ###

import heapq

a = []
while True:
    inp = input().split()
    if inp[0] == "insert":
        heapq.heappush(a, -int(inp[1]))
    elif inp[0] == "extract":
        print(-heapq.heappop(a))
    else:
        break
### BUGGY CODE ###

mod=10**9+7
n=int(input())
a=[format(int(i),'b') for i in input().split()]
d0=[0]*60
d1=[0]*60
ans=0
for i in a:
  d=i[::-1]
  l=len(i)
  for j in range(60):
    if j<l and d[j]=='1':
      d1[j]+=1
    else:
      d0[j]+=1
for j in range(60):
  ans+=d0[j]*d1[j]*(2**j)
  ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=[format(int(i),'b') for i in input().split()]
d0=[0]*60
d1=[0]*60
ans=0
for i in a:
  d=i[::-1]
  l=len(i)
  for j in range(60):
    if j<l and d[j]=='1':
      d1[j]+=1
    else:
      d0[j]+=1
for j in range(60):
  ans+=d0[j]*d1[j]*(2**j)
  ans%=mod
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(n-1-i):
        ans = ans + a[i]*a[i+1+j] % 1000000007
        if ans >= 1000000007:
            ans = ans - 1000000007

print(ans)

### FIXED CODE ###

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

s = sum(a)
ans = 0
mod = 10 ** 9 + 7

for i in range(n-1):
    s -= a[i]
    ans += a[i] * s % mod

ans = ans % mod
print(ans)
### BUGGY CODE ###

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

count = 0

while(k > 0):
  if a > 0:
    count += 1
    a -= 1
    k -= 1
  elif b > 0 :
    b -= 1
    k -= 1
  elif c > 0:
    count -= 1
    c -= 1
    k -= 1
  else:
    k -= 0
    
print(count)

### FIXED CODE ###

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

count = 0


if a > 0 and a <= k and k > 0:
  count = count + a
  k = k - a
elif a > 0 and a > k and k > 0:
  count = k
  k = 0

if b > 0 and b <= k and k > 0:
  k = k - b
elif b > 0 and b > k and k > 0:
  k = 0
  
if c > 0 and c <= k and k > 0:
  count = count - c
  k = k - c
elif c > 0 and c > k and k > 0:
  count = count - k
  k = 0
    
print(count)
### BUGGY CODE ###

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

cnt = 0
if K >= N:
    cnt = 0
elif 1 <= K < N:
    for i in range(K):
        H.remove(max(H))
    cnt = sum(H)

elif K == 0:
    cnt = sum(H)

print(cnt)

### FIXED CODE ###

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

cnt = 0
if K >= N:
    cnt = 0
elif 1 <= K < N:
    H_down = sorted(H, reverse = True)
    cnt = sum(H_down[K:])

elif K == 0:
    cnt = sum(H)

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

n, m = map(int, input().split())
for i in range(int(m / n), 0, -1):
    if not m % i:
        print(i)
        break

### FIXED CODE ###

from math import ceil
n, m = map(int, input().split())
for i in range(n, ceil(m**.5), 1):
    if not m % i:
        print(m//i)
        exit()
for i in range(int(min((m / n), m**.5)), 0, -1):
    if not m % i:
        print(i)
        break
### BUGGY CODE ###

N = int(input())

strings = []

for i in range(N):
    strings.append(''.join(sorted(list(input()))))

ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        if strings[i] == strings[j]:
            ans += 1

print(ans)

### FIXED CODE ###

from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0:
        return 1
    over = reduce(lambda x, y: x * y, range(n, n - r, -1))
    under = reduce(lambda x, y: x * y, range(1, r + 1))
    return over // under

N = int(input())

strings = {}
for i in range(N):
    key = ''.join(sorted(list(input())))
    strings.setdefault(key, 0)
    strings[key] += 1
ans = 0

for k, v in strings.items():
    if v > 1:
        ans += cmb(v, 2)

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

import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
#    C = Counter(A)
    U = [0] * (max(A)+1)
    ans = 0
    for e in A:
        U[e] += 1
    for e in A:
        t = e*2
        while t <= max(A):
            U[t] = 0
            t += e
        if U[e] > 1:
            U[e] = 0
    print(U.count(1))
if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)
### BUGGY CODE ###

N = int(input())
AAwIdx = [(i,A) for i, A in enumerate(map(int, input().split()))]
AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
answer = [[0]*(N+1) for _ in range(N+1)]
ans_all = 0
Idx_i = 0
Idx_f = N-1
for i in range(0,N):
    for no in range(i+1):
        idxi = i-no
        idxf = Idx_f-no
        ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1]
        if ans>answer[i+1-no][no]:
            answer[i+1-no][no] = ans
        ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1]
        if ans>answer[i-no][no+1]:
            answer[i-no][no+1] = ans
for i in range(N,N+1):
    for no in range(i+1):
        if ans_all<answer[i-no][no]:
            ans_all = answer[i-no][no]
  
print(ans_all)

### FIXED CODE ###

def solve():
    INF = float('inf')
 
    def max2(x, y): return x if x >= y else y
 
    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]
 
    As.sort(reverse=True)
 
    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))
 
    ans = 0
    for i in range(N+1):
        j = N-i
        ans = max2(ans, dp[i][j])
 
    print(ans)
 
 
solve()
### BUGGY CODE ###

import numpy as np
N = int(input())
A = [int(x) for x in input().split()]
solls = np.zeros(N)
for i in range(N):
    tmp = []
    tmp.append(solls[N-(i+1)])
    for j in range(N):
        if (j+2)*(N-(i+1)) <= (N-1):
            tmp.append(solls[(j+2)*(N-(i+1))])
    if sum(tmp)%2 != A[N-(i+1)]:
        solls[N-(i+1)] = 1

s = 0
ansint = []
for i in range(N):
    if solls[i] == 1:
        s = s+1
        ansint.append(i+1)

print(s)
print(*ansint) 

### FIXED CODE ###

import numpy as np
N = int(input())
A = [int(x) for x in input().split()]
solls = np.zeros(N+1)
A.insert(0,0)
solls[N//2+1:] = A[N//2+1:]

for i in range(N//2,0,-1):
    s = 0
    for j in range(2*i,N+1,i):
        s = s+solls[j]
    if (s%2 == 0)and(A[i] == 1):
        solls[i] = 1
    if (s%2 == 1)and(A[i] == 0):
        solls[i] = 1

s = 0
ls = []
for i in range(N+1):
    if solls[i] == 1:
        ls.append(i)
        s = s+1

print(s)
print(*ls)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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 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 = float('inf')
mod = 10 ** 9 + 7

a, b, m = MAP()
A = LIST()
B = LIST()
L = [LIST() for i in range(m)]

ans = []
for i in range(a):
    for j in range(b):
        ans.append(A[i] + B[i])

for x, y, c in L:
    ans.append(A[x-1] + B[y-1] - c)
print(min(ans))



exit()
s = input()
m= "hi"
# for i in range():
l = len(s) // 2
if l * m == s:
    print("Yes")
else:
    print("No")

# if s // 2



### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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 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 = float('inf')
mod = 10 ** 9 + 7

a, b, m = MAP()
A = LIST()
B = LIST()
A_s = sorted(A)
B_s = sorted(B)
# print(A)
# print(B)
L = [LIST() for i in range(m)]

ans = A_s[0] + B_s[0]
for x, y, c in L:
    # print(x, y, c)
    v = A[x-1] + B[y-1] - c
    if ans > v:
        ans = v
print(ans)


# exit()


# D = [[0] * b for i in range(a)]
# for x,y,c in L:
#     D[x-1][y-1] = max(D[x-1][y-1], c)
# ans = INF
# C = [[0] * b for i in range(a)]
# for i in range(a):
#     for j in range(b):
#         ans = min(A[i] + B[j] - D[i][j], ans)
        
# print(ans)

# # exit()

# # for x, y, c in L:
# #     C[x-1][y-1] = min(C[x-1][y-1], C[x-1][y-1]-c)

# # print(min(C))


# # #     ans.append(A[x-1] + B[y-1] - c)
# # # print(min(ans))



# # exit()
# # s = input()
# # m= "hi"
# # # for i in range():
# # l = len(s) // 2
# # if l * m == s:
# #     print("Yes")
# # else:
# #     print("No")

# # # if s // 2
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

odd = A[0::2]
even = A[1::2][::-1]

ans = even + odd

if n % 2 == 1:
    ans = ans[::-1]
    
print(*ans)
### BUGGY CODE ###

s = input()
k = int(input())


e=len(s)
l=[]
for i in range(e):
	for j in range(i+1, e+1):
		a = s[i:j]
		#print(i,j,a)
		l.append(a)


l=list(set(l))
l.sort()
#print(l)

print(l[k-1])


### FIXED CODE ###

s = input()
k = int(input())


e=len(s)
l=[]
for i in range(e):
	for j in range(i+1, e+1):
		a = s[i:j]
		if len(a)>k: break
		#print(i,j,a)
		l.append(a)


l=list(set(l))
l.sort()
#print(l)

print(l[k-1])
### BUGGY CODE ###

# coding: utf-8

def divisors(n):
    for i in range(2, n+1):
        if n % i == 0:
            yield i

def main():
    a, b = input().split()
    a, b = int(a), int(b)

    if a == 1 or b == 1:
        print(1)
        exit()

    if b > a:
        a, b = b, a
	
    relative_primes = []
    for div in divisors(b):
        if a % div != 0:
            continue
        flg = True
        for rp in relative_primes:
            if div % rp == 0:
                flg = False
                continue
        if flg:
            relative_primes.append(div)
    print(len(relative_primes)+1)
    

main()


### FIXED CODE ###

# coding: utf-8

def greatest_common_divisor(N, M):
    assert N >= M
    while M != 0:
        N, M = M, N%M
    return N

def prime_divisor(N):
    temp = N
    for n in range(2, int(-(-N**0.5//1))+1):
        if temp % n == 0:
            while temp % n == 0:
                temp //= n
            yield n
    if temp != 1:
        yield temp
        

def main():
    a, b = input().split()
    a, b = int(a), int(b)

    if a > b:
        a, b = b, a

    gcd = greatest_common_divisor(b, a)
    pdiv = [pd for pd in prime_divisor(gcd)]
    print(len(pdiv)+1)

main()
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())

cards = np.zeros(N) 
for j in range(M):
    L, R = map(int, input().split())
    for i in range(1, N+1):
        if cards[i-1] != 1:
            if L > i or R < i:
                cards[i-1] = 1

print(int(len(cards)-np.sum(cards)) )

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())

L = np.zeros(M)
R = np.zeros(M)
for j in range(M):
    L[j], R[j] = map(int, input().split())

if int(min(R) - max(L) + 1) < 0:
    print(0)
else:
    print(int(min(R) - max(L) + 1))
### BUGGY CODE ###

n = int(input())
s = str(input())
d = []
for i in range(0,n):
    c = s[0:i].count('W')+s[i+1:n].count('E')
    d.append(c)
print(min(d))

### FIXED CODE ###

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

a = [(0,0) for _ in range(n + 1)]
b = []
for i in range(n):
    if s[i] == "W":
        a[i+1] = (a[i][0] + 1,a[i][1])
    else:
        a[i+1] = (a[i][0],a[i][1] + 1)
    b.append(a[i+1][1]-a[i+1][0])
    
ans = s[0:b.index(max(b))].count('W') + s[b.index(max(b))+1:].count('E')
print(ans)
### BUGGY CODE ###

S = list(input())
Q = int(input())
t = 0
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        t += 1
    else:
        query[1] = int(query[1])
        if t % 2 == 1:
            if query[1] == 1:
                query[1] = 2
            else:
                query[1] = 1
        if query[1] == 1:
            S.insert(0, query[2])
        else:
            S.append(query[2])
if t % 2 == 1:
    S.reverse()
print("".join(S))


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
t = 0
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        t += 1
    else:
        query[1] = int(query[1])
        if t % 2 == 1:
            if query[1] == 1:
                query[1] = 2
            else:
                query[1] = 1
        if query[1] == 1:
            S.appendleft(query[2])
        else:
            S.append(query[2])
if t % 2 == 1:
    S.reverse()
print("".join(S))
### BUGGY CODE ###

def cal(a,b):
    if 4*a*b-A*(a+b)>0:
        return (A*a*b)/(4*a*b-A*(a+b))
    else:
        return -1
A = int(input())
for i in range(1,3501):
    for j in range(1,3501):
        t = cal(i,j)
        if t == -1:
            continue
        if t == int(t):
            print(i,j,int(t))
            exit()

### FIXED CODE ###

def cal(a,b):
    if 4*a*b-A*(a+b)>0:
        return (A*a*b)/(4*a*b-A*(a+b))
    else:
        return -1
A = int(input())
for i in range(1,3501):
    for j in range(i,3501):
        t = cal(i,j)
        if t == -1:
            continue
        if t == int(t):
            print(i,j,int(t))
            exit()
### BUGGY CODE ###

n = int(input())
A = [[c for c in input()] for _ in range(n)]

def chechTable(A, Shift):
    for i in range(n):
        for j in range(i):
            i_shift = i + Shift if i + Shift < n else i + Shift - n
            j_shift = j + Shift if j + Shift < n else j + Shift - n
            
            if A[i_shift][j] != A[j_shift][i]:
                return False
    return True

count = 0
for i in range(n):
    if chechTable(A, i):
        count += 1
print(count * n)

### FIXED CODE ###

n = int(input())
A = [input() for _ in range(n)]
A_t = [''] * n
for c in A:
    for i in range(n):
        A_t[i] += c[i]

def checkTable(shift):
    for i in range(n):
        if A_t[(i + shift) % n] != A[i][shift:] + A[i][:shift]:
            return False
    return True

count = 0
for i in range(n):
    if checkTable(i):
        count += 1
print(count * n)
### BUGGY CODE ###

# ki
from collections import deque

# input

n, q = map(int, input().split())
ln = [list(map(int, input().split())) for i in range(n-1)]
lq = [list(map(int, input().split())) for i in range(q)]

edge = [[] for i in range(n+1)]

for next in ln:
    parent = next[0]
    child = next[1]
    edge[parent].append(child)
    edge[child].append(parent)


score = [0]*(n+1)
visited = [False]*(n+1)

for q in lq:
    score[q[0]] += q[1]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    if not visited[node]:
        visited[node] = True
        for next in edge[node]:
            if not visited[next]:
                score[next] += score[node]
                que.append(next)

print(" ".join([str(n) for n in score][1:]))


### FIXED CODE ###

# ki
from collections import deque

# input

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

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

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

score = [0]*(n+1)
visited = [False]*(n+1)

for q in lq:
    score[q[0]] += q[1]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    if not visited[node]:
        visited[node] = True
        for next in edge[node]:
            if not visited[next]:
                score[next] += score[node]
                que.append(next)

print(" ".join([str(n) for n in score][1:]))
### BUGGY CODE ###

mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k=mi()
h=li()
dp = [0]*n
for i in range(0,n-1):
    ed = min(i+k+1,n)
    for j in range(i+1,ed):
        cost = dp[i]+abs(h[i] - h[j])
        if dp[j] == 0:
            dp[j] = cost
        elif dp[j] > cost:
            dp[j] = cost
print(dp[n-1])


### FIXED CODE ###

mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,k=mi()
h=np.array(li())
dp = np.array([0]*n)
for i in range(1,n):
    st = max(0,i-k)
    dp[i] = min(dp[st:i]+abs(h[i] - h[st:i]))
print(dp[n-1])
### BUGGY CODE ###

import sys

def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n-2) + lucas(n-1)

def main():
    input = sys.stdin.readline
    N = int(input())
    print(lucas(N))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    if N == 0:
        print(2)
        return 0
    if N == 1:
        print(1)
        return 0

    lucas = [0] * (N+1)
    lucas[0] = 2
    lucas[1] = 1
    for i in range(2, N+1):
        lucas[i] = lucas[i-2] + lucas[i-1]

    print(lucas[N])


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

n, m = (int(_) for _ in input().split())
e = [[int(i) for i in input().split()] for i in range(m)]

a_dict = {}
for pi,yi in e:
    a_dict[pi] = sorted([yj for pj,yj in e if(pi == pj)])

for pi,yi in e:
    print('{0:06d}'.format(pi)+'{0:06d}'.format(a_dict[pi].index(yi)+1))

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    # もとの値
    val = [[] for i in range(N+1)]
    for pi, yi in [[P[i], Y[i]] for i in range(M)]:
        val[pi].append(yi)

    for i in val:
        i.sort()


    a = sorted([[P[i], Y[i]] for i in range(M)], key=lambda x:(x[0],x[1]))

    for p, y in [[P[i], Y[i]] for i in range(M)]:
        c_id = bisect.bisect_left(val[p], y)
        print(str(p).zfill(6)+str(c_id+1).zfill(6))
    
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = [int()] * (M)  # type: "List[int]" 
    Y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()