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

S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len + 1)]
DP[S_len][0] = 1

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if S[i] != "?":
        for j in range(13):
            if DP[i + 1][j] != 0:
                DP[i][(j + int(S[i]) * num) % 13] += DP[i + 1][j] % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                DP[i][(j + k * num) % 13] += DP[i + 1][j] % 1000000007

print(DP[0][5] % 1000000007)



### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC94 C

from copy import deepcopy
n = int(input())
x = list(map(int,input().split()))

for i in range(n):
    y = deepcopy(x)
    y.remove(y[i])
    y.sort()
    print(y[n//2-1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC94 C

from copy import deepcopy
from operator import itemgetter
n = int(input())
x = list(map(int,input().split()))
y = sorted(x)
c1 = y[n//2-1]
c2 = y[n//2]
for i in x:
    if i < c2:
        print(c2)
    elif i >= c2:
        print(c1)
### BUGGY CODE ###

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1
for i in range(1,l):
    if L[i]=='1':
        ans+=(2**(cnt))*(3**(l-i-1))%(10**9+7)
        cnt+=1
        
print((ans+2**a)%(10**9+7))

### FIXED CODE ###

mod=10**9+7

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1

for i in range(1,l):
    if L[i]=='1':
        ans+=pow(2,cnt,mod)*pow(3,l-i-1,mod)
        cnt+=1
        
print((ans+pow(2,a,mod))%mod)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/24
Solved on 2019/3/
@author: shinjisu
"""


# ABC 056 C - Go Home
def getInt(): return int(input())
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob_TLE():
    d = Debug()
    d.off()
    X = getInt()
    d.dmp((X), 'X')
    pos = [0]
    for i in range(1, 10*9+1):
        nextPos = []
        for a in pos:
            nextPos.append(a-i)
            nextPos.append(a)
            nextPos.append(a+i)
        pos = nextPos
        d.dmp((pos), 'pos')
        if X in pos:
            break
    return i


def prob():
    d = Debug()
    d.off()
    X = getInt()
    d.dmp((X), 'X')
    pos = set([0])
    for i in range(1, 10**9+1):
        nextPos = set()
        for a in pos:
            nextPos.add(a-i)
            nextPos.add(a)
            nextPos.add(a+i)
        pos = nextPos
        #d.dmp((pos), 'pos')
        if X in pos:
            break
    return i


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/24
Solved on 2019/3/
@author: shinjisu
"""


# ABC 056 C - Go Home
def getInt(): return int(input())
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    X = getInt()
    d.dmp((X), 'X')
    sm = 0
    for i in range(1, 10**9+1):
        sm += i
        if X <= sm:
            break
    return i


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)
### BUGGY CODE ###

import numpy as np

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = np.array([0 for j in range(13)])
if s[0] == '?':
    for i in range(10):
        dp[i] = 1
else:
    num = int(s[0])
    dp[num] = 1

for i in range(1, n):
    dp_new = np.array([0 for j in range(13)])
    if s[i] == '?':
        for m in range(10):
            num = (m * 10**i) % 13
            dp_rolled = np.roll(dp, num)
            dp_new += dp_rolled
            dp_new %= mod
    else:
        num = (int(s[i]) * 10**i) % 13
        dp_rolled = np.roll(dp, num)
        dp_new += dp_rolled
        dp_new %= mod
    dp = dp_new

print(dp[5])

### FIXED CODE ###

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [[0 for j in range(13)] for i in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    num = int(s[0])
    dp[0][num] = 1

mul = 1
for i in range(1, n):
    mul = (mul*10) % 13
    if s[i] == '?':
        for m in range(10):
            num = (m * mul) % 13
            for j in range(13):
                dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod
    else:
        num = (int(s[i]) * mul) % 13
        for j in range(13):
            dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod

print(dp[n-1][5])
### BUGGY CODE ###

N = int(input())
P = [int(n) for n in input().split()]
c = 0
while P:
    r = min(P)
    P = P[:P.index(r)]
    c += 1
print(c)


### FIXED CODE ###

N = int(input())
P = [int(n) for n in input().split()]
c = 0
curr = 2*10**5+1
for p in P:
    if p < curr:
        curr = p
        c += 1
print(c)
### BUGGY CODE ###

n, k = map(int,input().split())
ans  = []

for i in range(n):
    x, y = map(int,input().split())
    ans += [x]*y

ans.sort()
print(ans[k-1])

### FIXED CODE ###

n, k = map(int,input().split())
ans  = []
x = 0

for i in range(n):
    ans.append(list(map(int,input().split())))

ans.sort()

for l in ans:
    x += l[1]
    if x < k:
        continue
    else:
        print(l[0])
        exit()
### BUGGY CODE ###

# AGC032 Problem-C
def special_case() :
    #Check 辺が4本出ているノードが2つあるケース
    #　　　2ノード間に4本の辺がある場合はNG
    #　　　2ノード間に2本の辺がある場合はOK (自分に戻るループがある)
    st = -1
    for i in range(0,n) :
        if check[i] == 4 :
            st = i
            break
    
    for i in edge[st] :
        p = i
        while (check[p]==2) :
            t1, t2 = edge[p]
            if t1 == st :
                p = t2
            else: 
                p = t1
        if p == st :
            return 0
    return -1

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

check = [0 for i in range(0,n)]
edge  = [[] for i in range(0,n)]
#table = [[0 for i in range (0,n)] for j in range (0,n)]
for i in range(0,m) :
    a, b = map(int,input().split())
    check[a-1] += 1
    check[b-1] += 1
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
#print (check)
#print(edge)

node4 = 0
node6 = 0
node_odd = 0
for i in range(0,n):
    if check[i] % 2 == 0:
        if check[i]==4 :
            node4 += 1
        if check[i]>=6 :
            node6 +=1
    else:
        node_odd += 1

if (node_odd != 0) :
    print ("No")
else :
    if ((node4 >= 3) or (node6 >=1)) :
        print ("Yes")
    elif (node4 == 2) :
        if special_case() == 0 :
            print ("Yes")
        else :
            print ("No")
    else :
        print ("No")


### FIXED CODE ###

# AGC032 Problem-C
def special_case() :
    #Check 辺が4本出ているノードが2つあるケース
    #　　　2ノード間に4本の辺がある場合はNG
    #　　　2ノード間に2本の辺がある場合はOK (自分に戻るループがある)
    st = -1
    for i in range(0,n) :
        if check[i] == 4 :
            st = i
            break
    
    for i in edge[st] :
        p0 = st
        p1 = i
        while (check[p1]==2) :
            t1, t2 = edge[p1]
            if t1 == p0 :
                p0 = p1
                p1 = t2
            else: 
                p0 = p1
                p1 = t1
        if p1 == st :
            return 0
    return -1

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

check = [0 for i in range(0,n)]
edge  = [[] for i in range(0,n)]
#table = [[0 for i in range (0,n)] for j in range (0,n)]
for i in range(0,m) :
    a, b = map(int,input().split())
    check[a-1] += 1
    check[b-1] += 1
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
#print (check)
#print(edge)

node4 = 0
node6 = 0
node_odd = 0
for i in range(0,n):
    if check[i] % 2 == 0:
        if check[i]==4 :
            node4 += 1
        if check[i]>=6 :
            node6 +=1
    else:
        node_odd += 1

if (node_odd != 0) :
    print ("No")
else :
    if ((node4 >= 3) or (node6 >=1)) :
        print ("Yes")
    elif (node4 == 2) :
        if special_case() == 0 :
            print ("Yes")
        else :
            print ("No")
    else :
        print ("No")
### BUGGY CODE ###

import fractions as math

def lcm(x,y):
    return (x * y) // math.gcd(x,y)

def main():
    (n,m) = map(int, input().split())
    s = input()
    t = input()

    nmlcm = lcm(n,m)
    nn = nmlcm // n
    mm = nmlcm // m

    for i in range(lcm(n,m)):
        if i%nn == 0 and i%mm == 0 and s[i//nn] != t[i//mm]:
            print(-1)
            return
    print(nmlcm)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions as math

def lcm(x,y):
    return (x * y) // math.gcd(x,y)

def main():
    (n,m) = map(int, input().split())
    s = input()
    t = input()

    nmlcm = lcm(n,m)
    nn = nmlcm // n
    mm = nmlcm // m
    nnmmlcm = lcm(nn,mm)

    for i in range(nmlcm // nnmmlcm):
        #print(nnmmlcm*i)
        if s[nnmmlcm*i//nn] != t[nnmmlcm*i//mm]:
            print(-1)
            return
    print(nmlcm)

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

n = int(input())
a = list(map(int,input().split()))
inf = 10 ** 9 + 7
total = 0

l = len(a)

for i in range(l - 1):
    for j in range(i + 1, l):
        total += ((a[i]*a[j]) % inf)

print(total % inf)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
inf = 10 ** 9 + 7

S = sum(a)
S2 = 0

for i in a:
    S2 += i * i

print((S*S - S2)//2 % inf)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = list(map(int, input().split()))
d = np.inf
dp = [d] * N
dp[0] = 0
cc = np.arange(1, N)
for i in cc:
  c =  np.arange(1, min(i, K)+1)
  dp[i] = min([dp[i-j]+np.abs(h[i]-h[i-j]) for j in c])
print(dp[N-1])


### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
words = []
for i in range(n):
    words.append(sorted(input()))

counter = 0
for i in range(n):
    for j in range(i+1, n):
        if words[i] == words[j]:
            counter += 1

print(counter)

### FIXED CODE ###

# -*- coding: utf-8 -*-

def my_sort(word):
    sorted_word_list = sorted(word)
    sorted_word = ""
    for letter in sorted_word_list:
        sorted_word += letter
    return sorted_word

n = int(input())
words = {}
for i in range(n):
    word = my_sort(input())
    if word in words.keys():
        words[word] += 1
    else:
        words[word] = 1

for key in words.keys():
    words[key] = max(words[key]*(words[key]-1)//2, 0)

print(sum(words.values()))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    n,a,b = map(int, input().split())
    def nCr(n, r, mod):#mod=10**9+7 
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    res = (2**n - 1)%mod
    x = nCr(n, a, mod)
    y = nCr(n, b, mod)
    print((res-x-y)%mod)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    n,a,b = map(int, input().split())
    def nCr(n, r, mod):#mod=10**9+7 
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    res = (2**n - 1)%mod
    x = nCr(n, a, mod)
    y = nCr(n, b, mod)
    print((res-x-y)%mod)

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

n = int(input())
p = list(map(int,input().split()))
ans = 0

for i in range(n-1):
    if min(p[:i+1]) > p[i+1]:
        ans += 1
print(ans+1)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
Min= float('inf')
for i in range(n-1):
    if Min > p[i]:
        Min = p[i]
    if Min > p[i+1]:
        ans += 1
print(ans+1)
### BUGGY CODE ###

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

s = set(l)

x=0
for i in s:
    y = l.count(i)
    if i <= y:
        x += y - i
    else:
        x += y

print(x)

### FIXED CODE ###

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

s=set(l)

import collections
c = collections.Counter(l)

x=0
for i in s:
    y = c[i]
    if i <= y:
        x += y - i
    else:
        x += y

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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1); V=[0]*(n+1)
    for i in range(1,n+1):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][c] iまでの品物で、重さがc以下
    dp=[[-1]*(w+1) for _ in range(n+1)]
    # メモ化再帰
    def solve(i,c):
        if(dp[i][c]!=-1): return dp[i][c]
        if(i==0):
            dp[i][c]=0
            return dp[i][c];
        if(c-W[i]>=0):
            dp[i][c]=max(solve(i-1,c-W[i])+V[i],solve(i-1,c))
            return dp[i][c]
        else:
            dp[i][c]=solve(i-1,c)
            return dp[i][c]
    print(solve(n,w))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*n; V=[0]*n
    for i in range(n):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][k] iまでの品物で、重さがk以下
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for k in range(w+1):
            if k-W[i-1]>=0:
                dp[i][k]=max(dp[i-1][k-W[i-1]]+V[i-1],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()
### BUGGY CODE ###

# DP(配るDP)
def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [float('inf')] * N
    dp[0] = 0
    for i in range(N - 1):
        dpi = dp[i]
        for j in range(1, K + 1):
            k = i + j
            if k > N - 1:
                break
            dp[k] = min(dp[k], dpi + abs(h[i + j] - h[i]))
    print(dp[N - 1])


main()


### FIXED CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])
### BUGGY CODE ###

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

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

change = []
for i in range(m):
	b, c = map(int, input().split())
	change.append([b,c])

change = sorted(change, key=lambda x: x[1])

for vals in change:
	b, c = vals
	for i in range(b):
		if a[i] < c:
			a[i] = c
		else:
			break
	a = sorted(a)

print(sum(a))

### FIXED CODE ###

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

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

change = []
for i in range(m):
	b, c = map(int, input().split())
	change.append([b,c])

change = sorted(change, key=lambda x: x[1], reverse=True)

cur = 0
done = False
for vals in change:
	b, c = vals
	for i in range(b):
		if a[cur] < c:
			a[cur] = c
		else:
			done = True
			break
		cur = (cur+1)%len(a)
	if done:
		break

print(sum(a))
### BUGGY CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = dict()
    for a in map(int, input().split()):
        A[a] = A.get(a,0)+1
    a = min(A.keys())
    A[a] -= 1
    if A[a] == 0:
        del A[a]

    for b in A.keys():
        B = A.copy()
        c_, c = a, b
        while c in B.keys():
            B[c] -= 1
            if B[c] == 0:
                del B[c]
            c_, c = c, c_^c
        if B == dict() and c == a:
            return 'Yes'
    return 'No'
if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = dict()
    for a in map(int, input().split()):
        A[a] = A.get(a,0) + 1
    if N % 3:
        if 0 in A and A[0] == N:
            return 'Yes'
        else:
            return 'No'
    else:
        if 0 in A and A[0] == N:
            return 'Yes'
        elif 0 in A and A[0] == N//3:
            if len(A) == 2:
                return 'Yes'
            else:
                return 'No'
        elif len(A) == 3:
            if len(set(A.values())) == 1:
                a,b,c = A.keys()
                if c == a^b:
                    return 'Yes'
                else:
                    return 'No'
            else:
                return 'No'
        else:
            return 'No'

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

# E - Coprime
from math import gcd

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

def prime(x):
    s = set()
    p = 2
    while x>1:
        if x%p==0:
            s.add(p)
            while x%p==0:
                x //= p
        p += 1
    return s

G = A[0]
pairwise = True
s = prime(A[0])

for i in range(1,N):
    a = A[i]
    t = prime(a)
    if len(s&t)>0:
        pairwise = False
    s = s|t
    G = gcd(G,a)

if pairwise:
    print('pairwise coprime')
elif G==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

# E - Coprime
from math import gcd

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
MAX = 10**6
L = [0]*(MAX+1)

def prime(x):
    global L
    p = 2
    while x>1:
        if L[x]==1:
            return False
        if x%p==0:
            while x%p==0:
                x //= p
            tmp = p
            while tmp<=MAX:
                L[tmp] = 1
                tmp += p
        p = p+1 if p*p<x else x   
    return True
        
G = A[0]
pairwise = True
_ = prime(A[0])

for i in range(1,N):
    a = A[i]
    if pairwise:
        pairwise = prime(a)
    G = gcd(G,a)

if pairwise:
    print('pairwise coprime')
elif G==1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

class Graph:
    def __init__(self, node_count, edge_count):
        self.node_count = node_count
        self.lst = [-1 for _ in range(node_count)]
        self.nxt = [0 for _ in range(edge_count)]
        self.to = [0 for _ in range(edge_count)]
        self.m = 0

    def add_edge(self, u, v, w):  # bidirection weight
        m = self.m
        self.nxt[m], self.lst[u], self.to[m] = self.lst[u], m, (v, w)
        self.m += 1

    def traverse(self, u):
        m = self.lst[u]
        while m != -1:
            yield self.to[m]
            m = self.nxt[m]


n,q=getints()
values = [0]*n
gr = Graph(n,2*n)

for _ in range(n-1):
    a,b=getints()
    a,b=a-1,b-1
    gr.add_edge(a,b,1)
    gr.add_edge(b,a,1)

for _ in range(q):
    u, p=getints()
    values[u-1] += p

def distribute(u, par, prev):
    stk = []
    stk.append((u, par, 0))
    while stk:
        u,par,prev=stk[-1]
        stk.pop()
        values[u] += prev
        for v, _ in gr.traverse(u):
            if v == par: continue
            stk.append((v,u,values[u]))

distribute(0, -1, 0)
print(" ".join(map(str, values)))

### FIXED CODE ###


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

class Graph:
    def __init__(self, node_count, edge_count):
        self.node_count = node_count
        self.lst = [-1 for _ in range(node_count)]
        self.nxt = [0 for _ in range(edge_count)]
        self.to = [0 for _ in range(edge_count)]
        self.m = 0

    def add_edge(self, u, v, w):  # bidirection weight
        m = self.m
        self.nxt[m], self.lst[u], self.to[m] = self.lst[u], m, (v, w)
        self.m += 1

    def traverse(self, u):
        m = self.lst[u]
        while m != -1:
            yield self.to[m]
            m = self.nxt[m]


n,q=getints()
values = [0]*n
gr = Graph(n,2*n)

for _ in range(n-1):
    a,b=getints()
    a,b=a-1,b-1
    gr.add_edge(a,b,1)
    gr.add_edge(b,a,1)

for _ in range(q):
    u, p=getints()
    values[u-1] += p

def distribute(u, par, prev):
    stk = []
    stk.append((u, par, 0))
    while stk:
        u,par,prev=stk[-1]
        stk.pop()
        values[u] += prev
        for v, _ in gr.traverse(u):
            if v == par: continue
            stk.append((v,u,values[u]))

distribute(0, -1, 0)
print(" ".join(map(str, values)))