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

import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [[0] * N for _ in range(N)]
tablelr = [[0] * N for _ in range(N)]
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i][j] = abs(a[j][0] - x) * a[j][2]
    tablelr[i][j] = abs(a[j][1] - y) * a[j][2]
zero = 0
for t in range(N + 1):
  res = float("inf")
  if zero:
    print(0)
    continue
  for c in combi([x for x in range(N)], t):
    for i in range(1 << t):
      table = [10 ** 20] * N
      for j in range(N):
        table[j] = min(abs(a[j][0]), abs(a[j][1])) * a[j][2]
      for j in range(t):
        if i & (1 << j):
          for k in range(N):
            table[k] = min(table[k], tableud[c[j]][k])
        else:
          for k in range(N):
            table[k] = min(table[k], tablelr[c[j]][k])
      res = min(res, sum(table))
  print(res)
  if res == 0: zero = 1

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
table = [0] * N
for k in range(N): table[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]
tableudi = [10 ** 12 for _ in range((1 << N) * N)]
tablelri = [10 ** 12 for _ in range((1 << N) * N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        ud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])
        lr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])
        tableudi[i * N + k] = min(tableudi[i * N + k], ud)
        tablelri[i * N + k] = min(tablelri[i * N + k], lr)
    else:
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
        tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 12] * (N + 1)
for t in range(1 << N):
  i = t + 0
  c = bin(t).count("1")
  while True:
    x = i + 0
    y = t ^ x
    rres = 0
    for j in range(N):
      rres += min(tableudi[x * N + j], tablelri[y * N + j])
    res[c] = min(res[c], rres)
    #print(t, res, rres)
    if i == 0: break
    i = (i - 1) & t
for r in res: print(r)
### BUGGY CODE ###

n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

ans = 0
for c in range(1,n-1):
  ab = n-c
  f = factorization(ab)
  tmp = 1
  for i in range(len(f)):
    tmp *= f[i][1]+1
  ans += tmp
  
print(ans+1)

### FIXED CODE ###

import itertools
import collections

N = int(input())

def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in xrange(2, n + 1):
        if table[i] == 0:
            for j in xrange(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n /= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

t = prime_factor_table(N)

ans = 0
for c in range(1,N-1):
  ab = N-c
  f = prime_factor(ab,t)
  v = f.values()
  tmp = 1
  for i in range(len(f)):
    tmp *= v[i]+1
  ans += tmp
  
print(ans+1)
### BUGGY CODE ###

class UnionFind():
	def __init__(self,size):
		self.table = [-1 for _ in range(size)]

	def find(self,x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def unite(self,x,y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] != self.table[s2]:
				if self.table[s1] < self.table[s2]:
					self.table[s2] = s1
				else:
					self.table[s1] = s2
			else:
				self.table[s1] += -1
				self.table[s2] = s1
		return

	def same(self,x,y):
		return self.find(x) == self.find(y)


N, M = map(int,input().split())
edges = [[] for _ in range(N)]

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

uf = UnionFind(N)

for u in edges[0]:
	if N-1 not in edges[0]:
		uf.unite(0,u)

for v in edges[N-1]:
	if 0 not in edges[N-1]:
		uf.unite(N-1,v)

print("POSSIBLE" if uf.same(0,N-1) == True else "IMPOSSIBLE")

### FIXED CODE ###

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

from1 = []
gotoN = []

for i in range(M):
	a, b = map(int,input().split())
	if a == 1:
		from1.append(b)
	if b == N:
		gotoN.append(a)

res = set(from1) & set(gotoN)

print("POSSIBLE" if len(res) > 0 else "IMPOSSIBLE")
### BUGGY CODE ###

H,W,N=map(int,input().split())
ans=[0 for i in range(10)]

data=[]
origin=[]
def check(a,b):
    if a>0 and a<H-1 and b>0 and b<W-1:return True
    else:return False

def count(a,b):
    for i in range(a-2,a+1):
        for j in range(b-2,b+1):
            if check(i,j):
                x=(i,j)
                data.append(x)
                if x not in origin:origin.append(x)
                
for k in range(N):
    a,b=map(int,input().split())
    count(a,b)

for x in origin:
    c = data.count(x)
    ans[c]+=1
zero = (H-2)*(W-2)-sum(ans)
ans[0]=zero
for i in range(10):
    print(ans[i])
    
#http://arc061.contest.atcoder.jp/data/arc/061/editorial.pdf

### FIXED CODE ###

from collections import defaultdict
H,W,N=map(int,input().split())
ans=[0 for i in range(10)]

data=defaultdict(int)
def check(a,b):
    if a>0 and a<H-1 and b>0 and b<W-1:return True
    else:return False

def count(a,b):
    for i in range(a-2,a+1):
        for j in range(b-2,b+1):
            if check(i,j):
                x=(i,j)
                data[x]+=1
                
for k in range(N):
    a,b=map(int,input().split())
    count(a,b)

for v in data.values():
    ans[v]+=1

ans[0]=(H-2)*(W-2)-sum(ans[1:])
for i in range(10):
    print(ans[i])
    
#http://arc061.contest.atcoder.jp/data/arc/061/editorial.pdf
#https://atcoder.jp/contests/abc045/submissions/4024831
#https://atcoder.jp/contests/abc045/submissions/4017890
### BUGGY CODE ###

import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
rel = [0]*len(ch)
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(len(ch)):
    for i in range(q):
        a = l[i][0]
        b = l[i][1]
        c = l[i][2]
        d = l[i][3]
        if ch[k][b-1]-ch[k][a-1]==c:
            rel[k]+=d
print(max(rel))

### FIXED CODE ###

import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
lch = len(ch)
rel = [0]*lch
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(lch):
    for i in range(q):
        if ch[k][l[i][1]-1]-ch[k][l[i][0]-1]==l[i][2]:
            rel[k]+=l[i][3]
print(max(rel))
### BUGGY CODE ###

import itertools

k = int(input())
comb = list(itertools.combinations_with_replacement([i for i in range(1,k+1)], 3))
ans = 0
for a,b,c in comb:
  n = a
  while n > 0:
    if a%n == 0 and b%n == 0 and c%n == 0:
      if len(set([a,b,c])) == 3:
        ans += 6 * n
      elif len(set([a,b,c])) == 2:
        ans += 3 * n
      else:
        ans += n
      break
    n -= 1

print(ans)

### FIXED CODE ###

import itertools

k = int(input())
comb = list(itertools.combinations_with_replacement([i for i in range(1,k+1)], 3))
ans = 0
for a,b,c in comb:
  permutation = len(set([a,b,c]))
  r = b % a
  while r > 0:
    b = a
    a = r
    r = b % a
    
  r = c % a
  while r > 0:
    c = a
    a = r
    r = c % a
    
  if permutation == 3:
    ans += 6 * a
  elif permutation == 2:
    ans += 3 * a
  else:
    ans += a
    
print(ans)
### BUGGY CODE ###

import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

import time
start = time.clock()
prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    for i in prime:
        if i > n // 2 + 1:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)
    
print(time.clock()-start)

### FIXED CODE ###

import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    temp = n // 2
    for i in prime:
        if i > temp:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
d = [0]*((N+1)**3)
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = i+j+k
            if s0:
                E += (i*N)/(s0**2) + d[x-1]*(i/s0)
                E += (j*N)/(s0**2) + d[x-N]*(j/s0)
                E += (k*N)/(s0**2) + d[x-N**2-N]*(k/s0)
            d[x] = E
print(d[B])

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
d = dict()
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
def decode(x):
    return [(x // ((N+1)**i))%(N+1) for  i in range(3)]
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = N-i-j-k
            if i:
                E += (i*N)/((N-s0)**2) + d[x-1]*(i/(N-s0))
            if j:
                E += (j*N)/((N-s0)**2) + d[x-N]*(j/(N-s0))
            if k:
                E += (k*N)/((N-s0)**2) + d[x-N**2-N]*(k/(N-s0))
            d[x] = E
print(d[B])
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    ans = min(ans, (r_val-l_val)*(t_val-u_val))
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

from itertools import permutations
import sys
INF = float('inf')
n, m, R = map(int, sys.stdin.readline().split())
r = [i-1 for i in map(int, sys.stdin.readline().split())]
dist = [[INF]*n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k]+dist[k][j]:
                dist[i][j] = dist[i][k]+dist[k][j]
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)


### FIXED CODE ###

from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

from scipy.sparse import csgraph
dist = csgraph.floyd_warshall(dist)
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                for k in range(13):
                    dp[1][(pow(10, i, 13) * j + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(pow(10, i, 13) * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


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

from fractions import gcd
k=int(input())
r1=[]
r2=[]
for l in range(1,k+1):
    for m in range(1,k+1):
        r1.append(gcd(l,m))

for i in range(len(r1)):
    for j in range(1,k+1):
        r2.append(gcd(r1[i],j))

print(sum(r2))

### FIXED CODE ###

from fractions import gcd
k=int(input())
l=[]
dp=[[0]*(k+1) for i in range(k+1)]

for i in range(1,k+1):
    for j in range(1,k+1):
        dp[i][j]=gcd(i,j)
        l.append(gcd(i,j))
sum=0
for x in range(1,k+1):
    for y in range(len(l)):
        sum += int(dp[l[y]][x])
print(sum)
### BUGGY CODE ###

from math import ceil, log2
import sys


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

stx.sort(key=lambda x: x[2])

ans = [-1] * q
jump = [-1] * q
for s, t, x in stx:
    d_start = bisect_left(d, s - x)
    d_stop = bisect_left(d, t - x, lo=d_start)
    while d_start < d_stop:
        if jump[d_start] == -1:
            ans[d_start] = x
            jump[d_start] = d_stop
            d_start += 1
        else:
            d_start = jump[d_start]

for an in ans:
    print(an)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(n//r+1):
    for j in range(n//g+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            cnt+=1
print(cnt)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(n//r+1):
    for j in range(n//g+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

from functools import reduce
from operator import mul
N = int(input())
An = input().split()
An_int = list(map(int, An))
AnS = reduce(mul,An_int)

if AnS <= 10**18:
    print(AnS)
else:
    print("-1")

### FIXED CODE ###

import sys
N = int(input())
An = list(map(int,input().split()))
a = 1
if 0 in An:
    print("0")
    sys.exit()
else:
    for i in range(N):
        a *= An[i]
        if a > 10**18:
            print("-1")
            sys.exit()
    if a <= 10**18:
        print(a)
        sys.exit()
### BUGGY CODE ###

n=input()[::-1]
n+="0"
lt=len(n)
dp=[[float('inf') for _ in range(2)] for j in range(lt+1)]
dp[0][0]=0

for i in range(0,lt):
    for j in range(2):
        x=int(n[i])
        x+=j #繰り上がり処理，あとに+11でもOK
        for num in range(0,10):
            ni = i + 1
            nj = 0
            b=num-x
            if b<0:
                b+=10
                nj=1
            dp[ni][nj]=min(dp[ni][nj],dp[i][j]+num+b)

print(dp[lt][0])

### FIXED CODE ###

n=input()[::-1]
n+="0"
lt=len(n)
dp=[[float('inf') for _ in range(2)] for j in range(lt+1)]
dp[0][0]=0

for i in range(0,lt):
    for j in range(2):
        x=int(n[i])
        x+=j #繰り上がり処理，あとに+11でもOK
        for num in range(0,10):
            ni = i + 1
            nj = 0
            b=num-x
            if b<0:
                b+=10
                nj=1
            dp[ni][nj]=min(dp[ni][nj],dp[i][j]+num+b)

print(dp[lt][0])
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in range(n):
    res += g//a[i]
    res %= mod
print(res)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in a:
    res += g//i
print(res%mod)
### BUGGY CODE ###

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

def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    # initialize count
    count = [0] * N
    for j in range(Q):
        count[p[j]-1] += x[j]
    # initialize tree vertice adjacency list
    adj_list = [ [] for i in range(N) ]
    for i in range(N-1):
        u, v = a[i] - 1, b[i] - 1
        adj_list[u] += [v]
        adj_list[v] += [u]
    # BFS from root, which is 0-th node
    explored = [False] * N
    myqueue = queue.Queue()
    explored[0] = True
    myqueue.put(0)
    while(not myqueue.empty()):
        u = myqueue.get()
        for v in adj_list[u]:
            if explored[v] == False:
                myqueue.put(v)
                explored[v] = True
                count[v] += count[u]
    print(' '.join([str(i) for i in count]))
    return


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
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    # initialize count
    count = [0] * N
    for j in range(Q):
        count[p[j]-1] += x[j]
    # initialize tree vertice adjacency list
    adj_list = [ [] for i in range(N) ]
    for i in range(N-1):
        u, v = a[i] - 1, b[i] - 1
        adj_list[u] += [v]
        adj_list[v] += [u]
    # BFS from root, which is 0-th node
    explored = [False] * N
    myqueue = queue.Queue()
    explored[0] = True
    myqueue.put(0)
    while(not myqueue.empty()):
        u = myqueue.get()
        for v in adj_list[u]:
            if explored[v] == False:
                myqueue.put(v)
                explored[v] = True
                count[v] += count[u]
    print(' '.join([str(i) for i in count]))
    return


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
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()