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

import sys


def main():
    input = sys.stdin.readline

    r, c, k = map(int, input().split())

    items = [[0] * (c + 1) for _ in range(r + 1)]
    for _ in range(k):
        i, j, v = map(int, input().split())
        items[i][j] = v

    # dp[i][j][m] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
    dp = [[[0] * 4 for _ in range(c + 1)] for _ in range(r + 1)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            for m in range(4):
                dp[i][j][m] = max(dp[i - 1][j][3], dp[i][j - 1][m])
            for m in reversed(range(3)):
                dp[i][j][m + 1] = max(dp[i][j][m + 1],
                                      dp[i][j][m] + items[i][j])

    print(dp[r][c][3])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    r, c, k = map(int, input().split())

    items = [[0] * (c + 1) for _ in range(r + 1)]
    for _ in range(k):
        i, j, v = map(int, input().split())
        items[i][j] = v

    # dp[m][i][j] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
    dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            for m in range(4):
                dp[m][i][j] = max(dp[3][i - 1][j], dp[m][i][j - 1])
            if items[i][j] > 0:
                for m in [2, 1, 0]:
                    dp[m + 1][i][j] = max(dp[m + 1][i][j],
                                          dp[m][i][j] + items[i][j])

    print(dp[3][r][c])


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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    for i in range(2, n):
        for div in make_divisors(a[i]):
            if(not div in numdct):  continue
            numdct[div] += 1
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] >= n - 1):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)


### FIXED CODE ###


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    dellist = []
    for i in range(2, n):
        for num in numdct.keys():
            if(a[i] % num != 0):
                numdct[num] -= 1
                if(numdct[num] == 0):
                    dellist.append(num)
        for d in dellist:
            del numdct[d]
        dellist.clear()
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] > 0):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[[] for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].append(j)
    tree[j].append(i)
    c[(i,j)]=k
    c[(j,i)]=k

result=[]
q,k=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
memo = defaultdict(lambda: -1) 

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(item,z)])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)







### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[set([]) for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].add(j)
    tree[j].add(i)
    c[(min(i,j),max(i,j))]=k

result=[]
q,k=map(int,input().split())

memo=[-1]*n

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(min(item,z),max(item,z))])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)
### BUGGY CODE ###

n,k=list(map(int,input().split()))
h=[]
d=[0]*(n-1)
ans=10**9

for i in range(n):
  h.append(int(input()))
h=sorted(h)

for i in range(n-1):
  d[i]=h[i+1]-h[i]
  
for i in range(n-k+1):
  tmp=sum(d[i:i+k-1])
  ans=min(ans,tmp)

print(ans)

### FIXED CODE ###

n,k=list(map(int,input().split()))
h=[int(input()) for i in range(n)]
h.sort()
print(min(h[i+k-1]-h[i] for i in range(n-k+1)))
### BUGGY CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0, a.count(1), a.count(2), a.count(3)]
    floatN = N*1.0
    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(N+1)]
    for k in range(A[3]+1):
        for j in range(A[2]+A[3] + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[A[1]][A[2]][A[3]])
main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    r, g, b, n = get_li()
    ans = 0
    for x in range(n // r + 1):
        for y in range(n // g + 1):
            z = n - r * x - g * y
            if z % b != 0 or z < 0:
                continue
            ans += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    r, g, b, n = get_li()
    ans = 0
    for x in range(n // r + 1):
        for y in range(n // g + 1):
            z = n - r * x - g * y
            if z % b != 0 or z < 0:
                continue
            ans += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


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

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

# input
N = int(input())
L = list(map(int, input().split()))

# solve
ans = 0
L.sort()
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[k] < L[j] + L[i]:
                ans += 1

# output
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect

# input
N = int(input())
L = list(map(int, input().split()))

# solve
ans = 0
L.sort()
for i in range(N):
    for j in range(i + 1, N):
        r = bisect.bisect_left(L, L[i] + L[j])
        l = j + 1
        ans += max(0, r - l)

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

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

if len(set(a)) == 1:
    print(a[0])
else:
    a.sort()
    count = 0
    while(1):
        count = count + 1
        for i in range(1, len(a)):
            x = a[i] + count
            for j in range(i):
                x = x % a[i-1-j]
        if x == 0:
            break

    print(count)


### FIXED CODE ###

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


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


ans = gcd(a[0], a[1])

for i in range(2, len(a)):
    ans = gcd(ans, a[i])

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

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

visited = [False] * N
def dfs(v, acc):
    visited[v] = True
    count[v] += acc
    for u in adj[v]:
        if visited[u]:
            continue
        dfs(u, count[v])

dfs(0, 0)
print(" ".join(map(str, count)))

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

visited = [False] * N
def dfs(v):
    visited[v] = True
    for u in adj[v]:
        if visited[u]:
            continue
        count[u] += count[v]
        dfs(u)

dfs(0)
print(*count)
### BUGGY CODE ###

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

ans = B - A + 1

st = set()

i = 1
while i * C <= B:
  if i * C >= A:
    ans -= 1
    st.add(i*C)
  i+=1
  
i = 1
while i * D <= B:
  if i * D >= A:  
    if not i*D in st:
      ans -= 1
  i += 1
  
print(ans)

### FIXED CODE ###

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

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

g = gcd(C, D) if C < D else gcd(D, C)
ansB = B-B//C-B//D+B//(C*D//g)
ansA = A - 1 - (A-1)//C - (A-1)//D + (A-1)//(C*D//g)
print(ansB-ansA)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a = [aa-i-1 for i, aa in enumerate(a)]
answer = 100000000
for b in range(min(a), max(a)+1):
  res = 0
  for aa in a:
    res += abs(aa-b)
  answer = min(answer,res)
print(answer)

### FIXED CODE ###

import math
import statistics
n = int(input())
a = list(map(int,input().split()))
a = [aa-i-1 for i, aa in enumerate(a)]
answer = n*10**20
median_low = statistics.median_low(a)
median_high = statistics.median_high(a)

for m in (median_low,median_high):
  ans=0
  for aa in a:
    ans += abs(aa-m)
  answer = min(ans,answer)
print(answer)
### BUGGY CODE ###

n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]

cnt = 0

def binarysearch(x, l):
	mi = 0
	ma = len(l) - 1
	
	while mi != ma:
		tmp = (mi + ma) // 2
		
		if l[tmp] == x:
			return tmp
		elif l[tmp] < x:
			mi = tmp + 1
		else:
			ma = tmp - 1
	else:
		if x == l[mi]:
			return mi
		else:
			return -1
	
	

for x in t:
	if binarysearch(x, s) != -1:
		cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]

cnt = 0

def binarysearch(x, l):
	mi = 0
	ma = len(l) - 1
	
	while mi < ma:
		tmp = (mi + ma) // 2
		
		if l[tmp] == x:
			return tmp
		elif l[tmp] < x:
			mi = tmp + 1
		else:
			ma = tmp - 1
	
	else:
		if mi == ma:
			if x == l[mi]:
				return mi
			else:
				return -1
		else:
			if x == l[mi]:
				return mi
			elif x == l[ma]:
				return ma
			else:
				return -1
	
	

for x in t:
	if binarysearch(x, s) != -1:
		cnt += 1

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

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    L=[[0]*w for _ in range(h)]
    R=[[0]*w for _ in range(h)]
    U=[[0]*w for _ in range(h)]
    D=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if S[i][j]=='#':
                L[i][j]=0
                U[i][j]=0
                continue
            if i==0:U[i][j]=1
            else:U[i][j]=U[i-1][j]+1
            if j==0:L[i][j]=1
            else:L[i][j]=L[i][j-1]+1
    for i in range(h-1,-1,-1):
        for j in range(w-1,-1,-1):
            if S[i][j]=='#':
                R[i][j]=0
                D[i][j]=0
                continue
            if i==h-1:D[i][j]=1
            else:D[i][j]=D[i+1][j]+1
            if j==w-1:R[i][j]=1
            else:R[i][j]=R[i][j+1]+1 
    X=[[l+r+u+d-3 for l,r,u,d in zip(ll,rr,uu,dd)] for ll,rr,uu,dd in zip(L,R,U,D)]
    print(max([max(x) for x in X]))


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    L=[[0]*w for _ in range(h)]
    R=[[0]*w for _ in range(h)]
    U=[[0]*w for _ in range(h)]
    D=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if S[i][j]=='#':
                L[i][j]=0
                U[i][j]=0
                continue
            if i==0:U[i][j]=1
            else:U[i][j]=U[i-1][j]+1
            if j==0:L[i][j]=1
            else:L[i][j]=L[i][j-1]+1
    for i in range(h-1,-1,-1):
        for j in range(w-1,-1,-1):
            if S[i][j]=='#':
                R[i][j]=0
                D[i][j]=0
                continue
            if i==h-1:D[i][j]=1
            else:D[i][j]=D[i+1][j]+1
            if j==w-1:R[i][j]=1
            else:R[i][j]=R[i][j+1]+1 
    X=[[l+r+u+d-3 for l,r,u,d in zip(ll,rr,uu,dd)] for ll,rr,uu,dd in zip(L,R,U,D)]
    print(max([max(x) for x in X]))


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

"""
python3 main.py < input.txt
"""
import math
import itertools as it

X,Y,Z,K=map(int, input().split())
A=list(map(int, input().split()))+[0]
A.sort(reverse=True)
B=list(map(int, input().split()))+[0]
B.sort(reverse=True)
C=list(map(int, input().split()))+[0]
C.sort(reverse=True)

def abc(x): return A[x[0]]+B[x[1]]+C[x[2]]
def cand(c): 
    x,y,z=c[0],c[1],c[2]
    return [(x+1,y,z),(x,y+1,z),(x,y,z+1)]
dp={1:(0,0,0)}
dpV={(0,0,0)}
def f(k):
    if k in dp:
        return abc(dp[k])
    candidates=list(it.chain.from_iterable([cand(dp[i]) for i in range(1,k)]))
    #print(candidates)
    candidates=list(filter(lambda x: (x not in dpV) and x[0]<X and x[1]<Y and x[2]<Z, candidates))
    #print(candidates)
    dp[k]=max(candidates,key=abc)
    dpV.add(dp[k])
    return abc(dp[k])
    
for i in range(1,K+1):
    print(f(i))

### FIXED CODE ###

"""
python3 main.py < input.txt
"""
import math
import itertools as it
import heapq

X,Y,Z,K=map(int, input().split())
A=list(sorted(map(int, input().split()), reverse=True))
B=list(sorted(map(int, input().split()), reverse=True))
C=list(sorted(map(int, input().split()), reverse=True))

def evaluate(x,y,z): return (-A[x]-B[y]-C[z], x,y,z)

Q=[]
heapq.heappush(Q, evaluate(0,0,0))
for i in range(1,K+1):
    (e,x,y,z) = heapq.heappop(Q)
    print(-e)
    if x+1 < X and evaluate(x+1, y, z) not in Q:
        heapq.heappush(Q, evaluate(x+1, y, z))
    if y+1 < Y and evaluate(x, y+1, z) not in Q:
        heapq.heappush(Q, evaluate(x, y+1, z))
    if z+1 < Z and evaluate(x, y, z+1) not in Q:
        heapq.heappush(Q, evaluate(x, y, z+1))
### BUGGY CODE ###

import itertools
def solve():
    N = int(input())
    S = input()
    comb = list(itertools.combinations(list(S), 3))
    print(len(set((comb))))

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N = int(input())
    S = input()

    cnt = 0
    for i in range(1000):
        target = str(i).zfill(3)
        idx = 0
        for ch in S:
            if ch == target[idx]:
                idx += 1
                if idx == 3:
                    cnt += 1
                    break
    
    print(cnt)

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

#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    Q.append((0, (x1, y1), (+1, 0)))
    Q.append((0, (x1, y1), (-1, 0)))
    Q.append((0, (x1, y1), (0, +1)))
    Q.append((0, (x1, y1), (0, -1)))
    i = 0
    while i < len(Q):
        curr, (x, y), (dx, dy) = Q[i]
        elseflag = False
        for k in range(1, K+1):
            X = x+k*dx
            Y = y+k*dy
            if not (0 <= X < H):
                break
            if not (0 <= Y < W):
                break
            if dist[X][Y] < curr+1:
                break
            if c[X][Y] == "@":
                break
            dist[X][Y] = curr+1
            Q.append((curr+1, (X, Y), (dy, dx)))
            Q.append((curr+1, (X, Y), (-dy, -dx)))
        else:
            # breakしなかったなら、同一方向をヒープへ追加
            Q.append((curr+1, (X, Y), (dx, dy)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


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

#13:12
n,q = map(int,input().split())
import heapq
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,[s-x,t-x,x])
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,[tmp[2],tmp[1]])
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)

### FIXED CODE ###

#13:12
n,q = map(int,input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def cur(x):
    for i in range(len(neighbor[x])):
        p=neighbor[x][i]
        if p==parent[x]: continue
        parent[p]=x
        ans[p]+=ans[x]
        cur(p)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

cur(1)
print(*ans[1:])


### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

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


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])