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

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            m =  (i * j) % 2019
            if m < ans:
                ans = m
print(ans)

### FIXED CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            m =  (i * j) % 2019
            if m == 0:
                print(m)
                exit()
            elif m < ans:
                ans = m
print(ans)
### BUGGY CODE ###

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

m = 10 ** 9 + 7
def main():
    r = 0
    for i in range(n - 1):
        r += ((a[i] % m) * (sum(a[i+1:]) % m))
    print(r % m)
    return

main()


### FIXED CODE ###

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


m = 10 ** 9 + 7
def main():
    s = sum(a)
    ss = 0
    r = 0
    for nn in range(n):
        ss += a[nn]
        r += a[nn] * (s - ss)
    print(r % m)
    return

main()
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
F = sorted([int(i) for i in input().split()])
OK = 10**12
NG = -1

while OK-NG > 1:
    mid = (OK+NG)//2
    cnt = 0
    for a, f in zip(A, F):
        if a*f > mid:
            cnt += math.ceil((a*f-mid)/f)
    if cnt <= K:
        OK = mid
    else:
        NG = mid
print(OK)


### FIXED CODE ###

N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()], reverse=True)

if sum(A) <= K:
    print(0)
    exit()
else:
    OK = 10**12
    NG = -1

    while OK-NG > 1:
        mid = (OK+NG)//2
        cnt = 0

        for i, a in enumerate(A):
            cnt += max(0, a-mid//F[i])
        if cnt <= K:
            OK = mid
        else:
            NG = mid

print(OK)
### BUGGY CODE ###

n = int(input())
s = []
count = 0
for i in range(n):
    s1 = list(input())
    s1.sort()
    "".join(s1)
    count = count + s.count(s1)
    s.append(s1)
print(count)

### FIXED CODE ###

n = int(input())
s = []
count = 0
for i in range(n):
    s1 = list(input())
    s1.sort()
    s1 = "".join(s1)
    s.append(s1)
s.sort()
s2 = list(set(s))
s2.sort()
if len(s) == len(s2):
    print("0")
else:
    j1 = 0
    j2 = 0
    count1 = 0
    while j1 < n and j2 < len(s2):
        if s[j1] == s2[j2]:
            count1 = count1 + 1
            j1 = j1 + 1
        else:
            count = count + int(count1*(count1-1)/2)
            j2 = j2 + 1
            count1 = 0
    count = count + int(count1*(count1-1)/2)
    print(count)
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    INF = 1000000005
    dp = [INF for _ in range(H + 1)]
    dp[0] = 0
    for i in range(0, H + 1):
        for j in range(N):
            k = 0
            while i + k * A[j] < H:
                dp[i + k * A[j]] = min(dp[i + k * A[j]], dp[i] + k * B[j])
                k += 1
            dp[H] = min(dp[H], dp[i] + k * B[j])

    print(dp[H])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, N = map(int, input().split())
    A = [0 for _ in range(N)]
    B = [0 for _ in range(N)]
    for i in range(N):
        a, b = map(int, input().split())
        A[i] = a
        B[i] = b

    INF = 1000000005
    dp = [[INF for _ in range(H + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i + 1][min(j + A[i], H)] = min(dp[i + 1]
                                              [min(j + A[i], H)], dp[i + 1][j] + B[i])

    print(dp[N][H])


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

p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*pow(x,(m-1)//2)**2)%p
def f(i):
    tot = 0
    for k in range(i+1):
        tot = (tot + (((2**k)%p)*A[i]*B[k]*B[i-k])%p)%p
    return tot
L = input().strip()
N = len(L)
A = [1 for _ in range(N)]
for i in range(2,N):
    A[i] = (i*A[i-1])%p
B = [1 for _ in range(N)]
B[N-1] = pow(A[N-1],p-2)
for i in range(N-2,1,-1):
    B[i] = (B[i+1]*(i+1))%p
C = [0 for _ in range(N)]
for i in range(1,N):
    if L[i-1]=="1":
        C[i] = C[i-1]+1
    else:
        C[i] = C[i-1]
tot = 0
for i in range(N):
    if L[i]=="1":
        tot = (tot+f(N-1-i)*2**C[i])%p
if L[N-1]=="0":
    tot = (tot+2**C[N-1])%p
else:
    tot = (tot+2**(C[N-1]+1))%p
print(tot)

### FIXED CODE ###

p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*pow(x,(m-1)//2)**2)%p
L = input().strip()
N = len(L)
C = [0 for _ in range(N)]
for i in range(1,N):
    if L[i-1]=="1":
        C[i] = C[i-1]+1
    else:
        C[i] = C[i-1]
tot = 0
for i in range(N):
    if L[i]=="1":
        tot = (tot+pow(3,N-1-i)*pow(2,C[i]))%p
if L[N-1]=="0":
    tot = (tot+pow(2,C[N-1]))%p
else:
    tot = (tot+pow(2,C[N-1]+1))%p
print(tot)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    head, tail = str(i)[0], str(i)[-1]
    if tail == "0":
        continue
    if head == tail:
        ans += 1
    if int(tail + head) <= N:
        ans += 1
    if len(str(N))-2 >= 1 or head == tail:
        for num in range(len(str(N))-2, 0, -1):
            for j in range(int("9"*num), -1, -1):
                pad = str(j).zfill(num)
                if int(tail + pad + head) <= N:
                    # print(int(tail + pad + head))
                    ans += int(j) + 1
                    if num > 1:
                        ans += int((num - 1) * "1") * 10
                    break
            else:
                continue
            break    
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    head, tail = str(i)[0], str(i)[-1]
    if tail == "0":
        continue
    if head == tail:
        ans += 1
    if int(tail + head) <= N:
        ans += 1
    if len(str(N))-2 >= 1 or head == tail:
        num = len(str(N))-2
        if int(tail) <= int(str(N)[0]) and num > 0:
            if int(tail + "9"*(len(str(N))-2) + head) <= N:
                j = int("9"*(len(str(N))-2))
            else:
                if int(tail + str(N)[1:-1] + head) <= N:
                    j = int(str(N)[1:-1])
                else:
                    j = int(str(N)[1:-1]) - 1
            ans += int(j) + 1
        if num > 1:
            ans += int((num - 1) * "1") * 10
    # print(i, ans)
                    
print(ans)
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
Takahashi = C - B
Aoki = A - D
if Takahashi == 0: print ("Yes")
if Aoki == 0: print ("No")
else:
    while Takahashi != 0 or Aoki != 0:
        Takahashi -= B
        Aoki -= D
        if Takahashi == 0:
            print ("Yes")
            break
        if Aoki == 0: 
            print ("No")
            break

### FIXED CODE ###

A,B,C,D = map(int, input().split())
Takahashi=0
Aoki=0
while C-B>0:
    C-=B
    Takahashi+=1
while A-D>0:
    A-=D
    Aoki+=1
print("Yes") if Aoki>=Takahashi else print("No")
### BUGGY CODE ###

import fractions


def gcd(l):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a == 1:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()
ans = 0
for i in range(N):
    b = A[:i]+A[i+1:]
    g = gcd(b)
    if g > ans:
        ans = g
print(ans)


### FIXED CODE ###

import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
q = int(input())
for i in range(q):
    b, c = input().split()
    replace_a = [int(i.replace(b, c)) if int(i) == int(b) else int(i) for i in a]
    print(sum(replace_a))
    a = [str(j) for j in replace_a]


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
count_a = Counter(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    tmp = count_a[b]
    new = {c : tmp}
    count_a.update(new)
    del count_a[b]
    sum_a = sum_a - b * tmp + c * tmp
    print(sum_a)
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
cd.sort(reverse=True)

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[i].append(j)

ans = []
temp= [[0, {-1}]]

while temp:
    q = temp.pop()
    if q[0] == N:
        ans.append(len(q[1])-1)
    else:
        for i in g[q[0]]:
            if not i in q[1]:
                s = q[1] | {i}
            else: s = q[1]
            temp.append([q[0]+1, s])
        temp.append([q[0]+1, q[1]])            
print(max(ans))

### FIXED CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
cd.sort()

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[j].append([pab[1],i])
        
ans = 0
s = set()

for gg in g:
    gg.sort(reverse=True)
    for ggg in gg:
        if ggg[1] in s:continue
        else:
            ans += 1
            s.add(ggg[1])
            break
print(ans)
### BUGGY CODE ###

import math

N = int(input())
s = [input() for i in range(N)]
mar = s
for i in range(N):
    mar = s[:]
    mar.pop(i)
    print(max(mar))

### FIXED CODE ###

N = int(input())
s = [int(input()) for i in range(N)]
ld = sorted(s, reverse=True)
D = int(s.index(ld[0]))

if N == 1:
    print(s[0])
else:
    for i in range(D):
        print(ld[0])
    print(ld[1])
    for i in range(N-D-1):
        print(ld[0])
### BUGGY CODE ###

n, a, b = map(int, input().split())
count = 0
bcount = 0
turn = 0
while count <= n:
    if turn % 2 == 0:
        if count + a <= n:
            count += a
            bcount += a
        else:
            bcount += n - count
            count += n - count

    else:
        if count + b <= n:
            count += b
        else:
            count += b
    turn += 1
print(bcount)


### FIXED CODE ###

n, a, b = map(int, input().split())
count = 0
bcount = 0
ab = a + b

k = int(n / ab)
amari = n - k * ab
bcount += k * a
if amari >= a:
    bcount += a
else:
    bcount += amari

print(bcount)
### BUGGY CODE ###

S = input()
Q = int(input())


flip = 0
for _ in range(Q):
    q = input()
    if q == '1':
        flip += 1
    else:
        _, f, c = q.split(' ')
        if f == '1' and (flip % 2) == 0:
            S = c + S
        elif f == '1' and (flip % 2) != 0:
            S = S + c
        elif f != '1' and (flip % 2) == 0:
            S = S + c
        else:
            S = c + S

if (flip % 2) == 0:
    print(''.join(S))
else:
    print(''.join(S[::-1]))


### FIXED CODE ###

S = input()
Q = int(input())


flip = 0
head = ""
for _ in range(Q):
    q = input()
    if q == '1':
        flip += 1
    else:
        _, f, c = q.split(' ')
        if f == '1' and (flip % 2) == 0:
            # S = c + S
            head = head + c
        elif f == '1' and (flip % 2) != 0:
            S = S + c
        elif f != '1' and (flip % 2) == 0:
            S = S + c
        else:
            # S = c + S
            head = head + c

if (flip % 2) == 0:
    head = head[::-1]
    S = head + S
else:
    S = S[::-1]
    S = S + head

print(S)
### BUGGY CODE ###

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

if K == 1:
    print(0)
    sys.exit()

current = N

while True:
    prev = current
    current = abs(current - K)
    next = abs(current - K)
    if prev == next:
        print(min(current, next))
        break


### FIXED CODE ###

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

if K == 1:
    print(0)
    sys.exit()

a = abs(N - K * (N // K + 1))
print(min(a, abs(a - K)))
### BUGGY CODE ###

import numpy as np
n=int(input())
s=list(input())
sr=[]
sg=[]
sb=[]
for ii in range(n):
    if s[ii]=="R":
        sr.append(ii)
    if s[ii]=="G":
        sg.append(ii)
    if s[ii]=="B":
        sb.append(ii)
sr.sort()
sg.sort()
sb.sort()
r=0
for ii in range(len(sr)):
  for jj in range(len(sg)):
    for kk in range(len(sb)):
      sl=set([abs(sr[ii]-sg[jj]),abs(sg[jj]-sb[kk]),abs(sb[kk]-sr[ii])])
      #print(sl)
      if len(sl)==3:
        r+=1
print(r)

### FIXED CODE ###

import numpy as np
n=int(input())
s=list(input())
sr=set()
sg=set()
sb=set()
for ii in range(n):
    if s[ii]=="R":
        sr.add(ii)
    if s[ii]=="G":
        sg.add(ii)
    if s[ii]=="B":
        sb.add(ii)
l=[len(sr),len(sg),len(sb)]
l.sort()

if l[0]==len(sr):
  s1=sr
  if l[1]==len(sg):
    s2=sg
    s3=sb
  else:
    s2=sb
    s3=sg
elif l[0]==len(sg):
  s1=sg
  if l[1]==len(sr):
    s2=sr
    s3=sb
  else:
    s2=sb
    s3=sr
else:
  s1=sb
  if l[1]==len(sr):
    s2=sr
    s3=sg
  else:
    s2=sg
    s3=sr
  
r=0
for ii in s1:
  for jj in s2:
    r+=len(s3)
    dt=abs(ii-jj)
    if ii+dt in s3:
      r-=1
    if ii-dt in s3:
      r-=1
    if jj+dt in s3:
      r-=1
    if jj-dt in s3:
      r-=1
    if (ii+jj)%2==0:
      if (ii+jj)//2 in s3:
        r-=1
      
print(r)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for k in range(n):
    c=0
    b=a.copy()
    a.pop(k)
    for i in list(set(a)):
        c+=(a.count(i)*(a.count(i)-1))/2
    print(int(c))
    a=b

### FIXED CODE ###

import collections as cl
import numpy as np
n=int(input())
a=list(map(int,input().split()))
b=cl.Counter(a)
a_=np.array(list(b.values()))
c=np.sum(a_*(a_-1)/2)
for k in range(n):
    x=b[a[k]]
    if x==2:
        print(int(c-1))
    elif x==1:
        print(int(c))
    else:
        print(int(c-(x-1)))
### BUGGY CODE ###

n, m = map(int, input().split())
al = map(int, input().split())
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1


keys = list(ad.keys())
keys.sort()
for i in range(m):
    b, c = map(int, input().split())
    
    if c == 1:
        break
    
    for a in keys:

        if a >= c:
            break
        
        k = 0
        if b > ad[a]:
            k = ad[a]
            ad[a] = 0
            b -= k
        else:
            ad[a] -= b
            k = b
            b = 0
        
        if c not in ad:
            ad[c] = k
        else:
            ad[c] += k
        
        keys = list(ad.keys())
        keys.sort()


sum = 0
for a in ad.keys():
    sum += a * ad[a]

print(sum)

### FIXED CODE ###

import heapq


n, m = map(int, input().split())
al = map(int, input().split())
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = map(int, input().split())
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

        if len(h) >= n:
            break


ans = sum( heapq.nlargest(n, h) )
print(ans)
### BUGGY CODE ###

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
for x in T:
	if x in S:
		count += 1
print "%d" % count

### FIXED CODE ###

n = int(raw_input())
S = set(raw_input().split())
q = int(raw_input())
T = set(raw_input().split())
print (len(S & T))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
if 1 in a:
    dp[1]=0
mod=10**9+7
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[None]*(n+1)
dp[0]=1
dp[1]=1
if 1 in a:
    dp[1]=0
for i in a:
    dp[i]=0
for i in range(2,n+1):
    if dp[i]!=0 :
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%(10**9+7))
### BUGGY CODE ###

H, W, A, B = map(int, input().split())

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

import functools
@functools.lru_cache(maxsize=None)
def rev(c, r):
    return mod_pow(fc[c] * fc[r] % m, m - 2, m)

def cr(c, r):
    return fc[c + r] * rev(c, r) % m


ans = 0
for c in range(B, W):
    ans = (ans + cr(c, H - 1 - A) * cr(W - 1 - c, A - 1)) % m
print(ans)

### FIXED CODE ###

H, W, A, B = map(int, input().split())

m = 10**9 + 7

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * ic[c] * ic[r] % m

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m
ic = [pow(x, m-2, m) for x in fc]

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))
        self.dic = {i:1 for i in range(n)}

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self[y] = x
        if x != y :
            self.dic[x] += self.dic[y]
            del self.dic[y]

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

    def fubensa(self) :
        s = sum(self.dic.values())
        return sum(i*(s-i) for i in self.dic.values())//2

uf = UnionFind(n)
ans = []
for a, b in reversed(ab) :
    ans.append(uf.fubensa())
    uf.union(a-1, b-1)
    
for a in reversed(ans) :
    print(a)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**5)

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))
        self.dic = {i:1 for i in range(n)}
        self.fubensa = n*(n-1)//2

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self[y] = x
        if x != y :
            self.fubensa -= self.dic[x]*self.dic[y]
            self.dic[x] += self.dic[y]
            del self.dic[y]

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

uf = UnionFind(n)
ans = []
for a, b in reversed(ab) :
    ans.append(uf.fubensa)
    uf.union(a-1, b-1)
    
for a in reversed(ans) :
    print(a)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, 10):
  for j in range(1, 10):
    a = 0
    b = 0
    for k in range(1, n+1):
      K = str(k)
      if int(K[0]) == i and int(K[-1]) == j:
        a += 1
      if int(K[0]) == j and int(K[-1]) == i:
        b += 1
    ans += a*b
print(ans)

### FIXED CODE ###

n = int(input())
li_a = []
for i in range(9):
  li_a.append([0,0,0,0,0,0,0,0,0])
for i in range(1, n+1):
  k = str(i)
  k0 = int(k[0])
  k1 = int(k[-1])
  if k0*k1 != 0:
    li_a[k0-1][k1-1] += 1
ans = 0
for i in range(9):
  for j in range(9):
    ans += li_a[i][j]*li_a[j][i]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  p -= 1
  ans[p] += x

def dfs(u, v):
  for v_ in g[v]:
    if v_ == u:
      continue
    else:
      ans[v_] += ans[v]
      dfs(v, v_)

dfs(0,0)
print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
from collections import deque
s = deque()
s.append(0)

while s:
  v = s.pop()
  for v_ in g[v]:
    ans[v_] += ans[v]
    s.append(v_)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

nums, jump = list(map(int,input().split()))
height = list(map(int,input().split()))
dp = [0 for i in range(nums)]
for i in range(nums):dp[i] = float("inf")
dp[0] = 0
for i in range(nums):
    for x in range(1,jump+1):
        if i+x >= nums: continue
        check = dp[i] + abs(height[i] - height[i+x])
        if check < dp[i+x]:
            dp[i+x] = check
print(dp[nums-1])

### FIXED CODE ###

import numpy as np

n, k = map(int,input().split())
h = list(map(int,input().split()))

h = np.array(h)
dp = np.zeros(n, dtype=int)

for i in range(1,n):
    m = max(0,i-k)
    dp[i] = min(dp[m:i] + np.abs(h[i] - h[m:i]))
print(dp[n-1])
### BUGGY CODE ###

import sys

def check_ans(s,x):
  if len(s)==0:
    return x==0
  
  dp=[[False for i in range(8001)] for j in range(len(s)+1)]
  dp[1][s[0]]=True
  for i in range(1,len(s)):
    for j in range(0,8001):
      if dp[i][j]:
        res=abs(j+s[i])
        res2=abs(j-s[i])
        dp[i+1][res]=True
        dp[i+1][res2]=True
  return dp[len(s)][x]

S = sys.stdin.readline().strip()
X,Y=map(int,input().split())
d=1
while S and S[0]=='F':
  S=S[1:]
  X-=1
if len(S)==0:
  if X==0 and Y==0:
    print("Yes")
  else:
    print("No")
  sys.exit()

nx=[]
ny=[]
X=abs(X)
Y=abs(Y)

while S:
  step=0
  while S and S[0]=='T':
    d*=-1
    S=S[1:]
  while S and S[0]=='F':
    step+=1
    S=S[1:]
  if step==0:
    break
  if d==1:
    nx.append(step)
  else:
    ny.append(step)

if check_ans(nx,X) and check_ans(ny,Y):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys

def check_ans(s,x):
  res=[0]
  for i in s:
    res = set([x + i for x in res]) | set([x - i for x in res])
  return x in res

S = sys.stdin.readline().strip()
X,Y=map(int,input().split())
d=1
while S and S[0]=='F':
  S=S[1:]
  X-=1
if len(S)==0:
  if X==0 and Y==0:
    print("Yes")
  else:
    print("No")
  sys.exit()

nx=[]
ny=[]
X=abs(X)
Y=abs(Y)

while S:
  step=0
  while S and S[0]=='T':
    d*=-1
    S=S[1:]
  while S and S[0]=='F':
    step+=1
    S=S[1:]
  if step==0:
    break
  if d==1:
    nx.append(step)
  else:
    ny.append(step)

if check_ans(nx,X) and check_ans(ny,Y):
  print("Yes")
else:
  print("No")