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

S = str(input())
l = [0]* len(S)
for i in range(len(S)):
    T = S[:(i + 1)]
    t = int(T)
    l[i] = t * 10 ** (len(S) - i - 1)%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
print(sum(m) + l.count(0))

### FIXED CODE ###

S = str(input())
l = [0]* len(S)
q = 1
l[0] = int(S[len(S) - 1])
for i in range(1,len(S)):
    t = int(S[len(S) - i - 1])
    q = q * 10 % 2019
    l[i] = (t*q + l[i - 1]%2019)%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
a = 0
for i in range(len(S)):
    if l[i] == 0:
        a += 1
    else:
        break
print(sum(m) + a)
### BUGGY CODE ###

def div(n):
    lower_div, upper_div = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_div.append(i)
            if i != n // i:
                upper_div.append(n // i)
        i += 1
    return lower_div + upper_div[::-1]

def main():
    n = int(input())
    A = list(map(int, input().split()))
    L = [0] * n
    b = []
    cnt = 0
    for i in reversed(range(n)):
        if A[i] != L[i] % 2:
            b.append(i+1)
            cnt += 1
            d = div(i + 1)
            for j in d:
                L[j-1] += 1
    print(cnt)
    print(*b)

main()


### FIXED CODE ###

def div(n):
    lower_div, upper_div = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_div.append(i)
            if i != n // i:
                upper_div.append(n // i)
        i += 1
    return lower_div + upper_div[::-1]

def main():
    n = int(input())
    A = list(map(int, input().split()))
    L = [0] * n
    b = []
    for i in reversed(range(n)):
        if A[i] != L[i] % 2:
            b.append(i+1)
            d = div(i + 1)
            for j in d:
                L[j-1] += 1
    print(len(b))
    print(*b)

main()
### BUGGY CODE ###

# review
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    OK = [True for i in range(10**6+1)]
    CNT = [0 for i in range(10**6+1)]
    for x in A:
        CNT[x] += 1
        for i in range(2, 10**6+1):
            if i*x > 10**6:
                break
            OK[i*x] = False
    for x in A:
        if CNT[x] == 1 and OK[x]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
visited=[False for i in range(10**6+1)]
ban=[False for i in range(10**6+1)]
from collections import Counter
A.sort()
D=dict(Counter(A))
for n in A:
    if visited[n]==False:
        visited[n]=True
        for j in range(2,10**6):
            if 10**6<n*j:
                break 
            ban[n*j]=True
ans=0
for n in A:
    if D[n]==1 and ban[n]==False:
        ans+=1
print(ans)
### BUGGY CODE ###

import math

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

N,Y = readInts()
o = Y

for x in range(Y//10000,-1,-1):
	o=Y-x*10000
	#print(Y,x,o)
	for y in range(o//5000,-1,-1):
		#print(y)
		o=Y-x*10000-y*5000
		for z in range(o//1000,-1,-1):
			#print(x,y,z)
			res = x*10000+y*5000+z*1000
			if res==Y and sum([x,y,z])==N:
				print(str(x)+" "+str(y)+" "+str(z))
				exit()

print("-1 -1 -1")

### FIXED CODE ###

import math

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

N,Y = readInts()
o = Y



for x in range(Y//10000,-1,-1):
	o=Y-x*10000
	#print(Y,x,o)
	for y in range(o//5000,-1,-1):
		#print(y)
		o=Y-x*10000-y*5000
		z=o//1000
		res = x*10000+y*5000+z*1000
		if x+y+z>N or res>Y:
			break
		if res==Y and x+y+z==N:
			print(str(x)+" "+str(y)+" "+str(z))
			exit()

print("-1 -1 -1")
### BUGGY CODE ###

n = int(input())
for i in range(1, 3501):
  for j in range(1, 3501):
    seed = 4 * i * j - n * i - n * j 
    if seed > 0:
      k = n * i * j / seed 
      if k % 1 == 0:
        print(i, j, int(k))
        exit()


### FIXED CODE ###

n = int(input())
for i in range(1, 3501):
  for j in range(1, 3501):
    seed = 4 * i * j - n * i - n * j 
    if seed > 0:
      k = n * i * j / seed 
      if k % 1 == 0:
        print(i, j, int(k))
        exit()
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0 for _ in range(Q)]
C = [0 for _ in range(Q)]
for i in range(Q):
  B[i], C[i] = map(int, input().split())
  
for i in range(Q):
  for j in range(N):
    if A[j] == B[i]:
      A[j] = C[i]
  print(np.sum(A))

### FIXED CODE ###

import collections
import numpy as np

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0 for _ in range(Q)]
C = [0 for _ in range(Q)]
for i in range(Q):
  B[i], C[i] = map(int, input().split())
  
a = collections.Counter(A)
S = np.sum(A)
for i in range(Q):
  S += (C[i]-B[i]) * a[B[i]]
  a[C[i]] += a[B[i]]
  a[B[i]] = 0

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

import bisect
from numpy import floor,sum
N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
    if A[N-1] >= A[N-2]:
        A[N-1] = A[N-1] / 2
        if A[N-1] < A[N-2]:
            bisect.insort_left(A,A[N-1])
            del A[-1]
B = floor(A)
print(int(sum(B)))

### FIXED CODE ###

import heapq
from numpy import ceil,sum
N,M = (int(x) for x in input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)
for i in range(M):
    t1 = heapq.heappop(A)
    t2 = t1 / 2
    heapq.heappush(A, t2)
B = ceil(A)
print(int(sum(B)*(-1)))
### BUGGY CODE ###

N,K = list(map(int,input().strip().split()))
hlist = []
ans = int(10e10)

for i in range(N):
    hlist.append(int(input()))

hlist.sort()

for i in range(N-K+1):
    low = min(hlist[i:i+K])
    high = max(hlist[i:i+K])
    ans = min(ans,(high-low))

print(ans)


### FIXED CODE ###

N,K = list(map(int,input().strip().split()))
ans = int(10e10)

hlist = [int(input()) for i in range(N)] 

hlist.sort()

for i in range(N-K+1):
    low = hlist[i]
    high = hlist[i+K-1]
    ans = min(ans,(high-low))

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

n = int(input())
l = list(map(int, input().split()))
ls = sorted(l)
a = [str(l.index(ls[i])+1) for i in range(n)]
print(' '.join(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0] * n
for i in range(n):
    s[a[i] - 1] = i + 1
print(*s)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        xx = x + dx
        yy = y + dy
        if xx < 0 or xx >= H:
            continue

        if yy < 0 or yy >= W:
            continue

        if checked[xx][yy] == -1:
            checked[xx][yy] = checked[x][y] + 1
            queue.append((xx, yy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]

print(ans)


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

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

import sys


def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    if l < h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r < h and a[r] > a[largest]:
        largest = r

    if largest != i:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[-1]
    a.pop()
    build_max_heap(a)
    return max


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print(extract_max(heap))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))


### FIXED CODE ###

import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


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

K, S = map(int, input().split())
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z >= 0 and z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

# %%

n, m = list(map(int, input().split()))
ary = sorted(list(map(int, input().split())), reverse=True)
bry = sorted(list(map(int, input().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):
        if (num in ary[i:]) & (num in bry[j:]):
            i += 1
            j += 1
        elif (num in ary[i:]) ^ (num in bry[j:]):
            if num in ary[i:]:
                cnt *= len(bry[:j]) % mod
                i += 1
            else:
                cnt *= len(ary[:i]) % mod
                j += 1
        else:
            na = len(ary[:i])
            nb = len(bry[:j])
            cnt *= (na * nb - (n * m - num)) % mod

    print(cnt % mod)


### FIXED CODE ###

import sys

# %%

n, m = list(map(int, sys.stdin.readline().split()))
ary = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
bry = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    ary.append(0)
    bry.append(0)

    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):

        if (num == ary[i]) and (num == bry[j]):
            i += 1
            j += 1

        elif (num == ary[i]) or (num == bry[j]):
            if num == ary[i]:
                cnt *= len(bry[:j])
                i += 1
            else:
                cnt *= len(ary[:i])
                j += 1

        else:
            # na = len(ary[:i])
            # nb = len(bry[:j])
            cnt *= (i * j - (n * m - num))

        cnt = cnt % mod

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

import sys

H,W=map(int,next(sys.stdin).split())
xs=[[0+(c!='#') for c in ln] for ln in map(str.strip,sys.stdin)]

#xs=[[0]*(W+1) for _ in range(H+1)]
ys=[[0]*(W) for _ in range(H)]


for i in range(H):
    for j in range(W):
        if xs[i][j]!=0:
            if j>0:
                xs[i][j]+=xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

#from pprint import pprint
#pprint(xs,width=60)
#print()
#pprint(ys,width=60)

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue

        if j+1<W and xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if i+1<H and ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)


### FIXED CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

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

N,Q = map(int,input().split())
S = 'Z'+input()
L = []
res = 0
for i in range(0,N+1):
    if S[i] == 'C' and S[i-1] == 'A':
        res += 1
    L.append(res)
for i in range(Q):
    l,r = map(int,input().split())
    print(max(L[l:r+1])-min(L[l:r+1]))

### FIXED CODE ###

import bisect

N,Q = map(int,input().split())
S = input()
L = []
for i in range(N):
    if S[i:i+2] == 'AC':
        L.append(i)
for i in range(Q):
    l,r = map(int,input().split())
    a = bisect.bisect_left(L,l-1)
    b = bisect.bisect_right(L,r-2)
    print(b-a)
### BUGGY CODE ###

n=int(input())
nl=list(map(int,input().split()))
ans=1
for s in range(n):
  ans=ans*nl[s]
if ans>10**18:
  ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
nl=list(map(int,input().split()))
nl.sort()
ans=1
for s in range(n):
  ans=ans*nl[s]
  if ans>10**18:
    ans=-1
    break
print(ans)
### BUGGY CODE ###

n = list(map(int, input().split()))
b, m, s = sorted(n)[::-1]
cnt = 0
while b != m or m != s or s != b:
    m_s = m - s
    b_m = b - m
    if m_s % 2 == 0 and m < b and m_s != 0:
        cnt += m_s // 2
        s += m_s
    elif m_s % 2 == 1 and m < b:
        cnt += 1
        s += 1
        b += 1
    elif m_s == 0 and m < b:
        cnt += b_m
        m += b_m
        s += b_m
print(cnt)

### FIXED CODE ###

a = list(map(int, input().split()))
s, m, b = sorted(a)
cnt = 0
m_s = m - s
cnt += b - m
cnt += m_s // 2

if m_s % 2 == 1:
    cnt += 2
print(cnt)
### BUGGY CODE ###

from itertools import combinations as comb
import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    hh = len(li)
    tmp = [0]*hh
    cnt = 0
    for i in range(w):
        for j in range(hh):
            if li[j, i]>k:
                return -1
            if tmp[j]+li[j, i]>k:
                cnt += 1
                for x in range(hh):
                    tmp[x] = li[x, i]
                break
            tmp[j] += li[j, i]
    return cnt

ans = 1000000
l = np.sum(s, axis=0, keepdims=True)
cnt = count(l)
if cnt>=0:
    ans = min(ans, cnt)

li = list(range(1, h))
for i in range(1, h):
    combs = list(comb(li, i))
    for cmb in combs:
        r = 0
        l = []
        for j in cmb:
            l.append(np.sum(s[r:j, :], axis=0))
            r = j
        l.append(np.sum(s[r:, :], axis=0))
        cnt = count(np.vstack(l))
        if cnt>=0:
            ans = min(ans, cnt+i)
print(ans)


### FIXED CODE ###

import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = len(li)-1
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            if cnt >= ans:
                return -1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    if ans <= len(l)-1:
        continue
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

m = 10000000
NIL = -1

def h1(key):
    return key % m

def h2(key):
    return 1 + (key % (m - 1))

def h(key, i):
    return (h1(key) + i * h2(key)) % m

def insert(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == NIL:
            t[j] = key
            return j
        else:
            i += 1

def find(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == key:
            return j
        elif t[j] == NIL or i >= m:
            return NIL
        else:
            i += 1

def convert(word):
    result = ""
    for i in word:
        if i == "A":
            result += "1"
        elif i == "T":
            result += "2"
        elif i == "G":
            result += "3"
        else:
            result += "4"
    return int(result)


t = [NIL]*m
n = int(input())
for i in range(n):
    com = input().split()
    key = convert(com[1])
    if com[0] == "insert":
        insert(t, key)
    else:
        if find(t, key) != NIL:
            print("yes")
        else:
            print("no")



### FIXED CODE ###

n = int(input())
d = set()

for i in range(n):
    com = input().split()
    if com[0] == "insert":
        d.add(com[1])
    else:
        print("yes" if com[1] in d else "no")
### BUGGY CODE ###

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

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

C = [0] * M
if N == 1:
    for i in range(M):
        A[0] = A[0] // 2
    print(A[0])
    exit(0)


while(M > 0):
    A.sort(reverse=True)
    k = min((A[0] // A[1]), M)
    A[0] = A[0] // (2 ** k)
    M -= k

print(sum(A))


### FIXED CODE ###

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

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

hq = []

for i in range(N):
    heapq.heappush(hq, -(A[i]))


while(M):
    k = heapq.heappop(hq) * -1
    k = k // 2
    heapq.heappush(hq, -k)
    M -= 1
ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

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

N = int(input())

p = 1

for i in range(N):
    i += 1
    p *= i

print(p % (pow(10, 9) + 7))


### FIXED CODE ###

N = int(input())

p = 1

for i in range(N):
    i += 1
    p *= i
    p %= 10**9 + 7

print(p)
### BUGGY CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
A_counters = Counter(A)

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

nums = set()
ans = 0
for a in A:
    if make_divisors(a) and A_counters[a] == 1:
        ans += 1
    nums.add(a)
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A_counters = Counter(A)
A.sort()
A_set = set(A)
ans = 0
for a in A:
    if a in A_set:
        if A_counters[a] == 1:
            ans += 1
        for i in range(1, A[-1] // a + 1):
            if a * i in A_set:
                A_set.remove(a * i)
print(ans)
### BUGGY CODE ###

import copy
N = int(input())
X = list(map(int,input().split()))
length = len(X)
 
 
for i in range(N):
    x = copy.copy(X) 
    x.pop(i)
    x.sort()
    print(x[int(length/2)-1])
    # print(x,X)

### FIXED CODE ###

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

sortx = sorted(X)
bef = sortx[N//2-1]
aft = sortx[N//2]
for i in X:
        print(aft if i <= bef else bef)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*(N+1)
for i in range(Q):
    p0, p1 = mi()
    cnt[p0] += p1

#隣接リスト作成
adj = [[] for i in range(N+1)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

global ans
ans = [0]*(N+1)

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(1, 1)

for i in range(1, N+1):
    print(ans[i], '', end='')

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


for i in range(1, N+1):
    print(ans[i], ' ', end='')
'''

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

que = deque()
ans = [0]*N

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        if next != v[0]:
            que.append((v[1], next))

for k in ans:
    print(k, '', end='')