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

n=int(input())
l=list(input())
ans=0
for i in range(10):
  for j in range(10):
    for k in range(10):
      now=str(i)
      count=0
      b=True
      f=1
      while count<n and b:
        if l[count]==now:
          if f==1:
            now=str(j)
            f+=1
          elif f==2:
            now=str(k)
            f+=1
          else:
            b=False
            ans+=1
        count+=1
print(ans)
            


### FIXED CODE ###

n=int(input())
w=input()
d1={}
d2={}
d3={}
for i in range(0,10):
  d1[str(i)]=0
  for j in range(10):
    d2[str(i)+str(j)]=0
    for k in range(10):
      d3[str(i)+str(j)+str(k)]=0
for i in range(len(w)):
  for j in range(10):
    for k in range(10):
      if d2[str(j)+str(k)]>0:
        d3[str(j)+str(k)+w[i]]=1
  for j in range(10):
    if d1[str(j)]>0:
      d2[str(j)+w[i]]=1
  d1[w[i]]+=1
ans=0
for i in d3:
  if d3[i]>0:
    ans+=1
print(ans)
### BUGGY CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


if __name__ == '__main__':
    solve1()


### FIXED CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


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

from collections import defaultdict
from heapq import heappush, heappop, heapify

class Solution:
    def main(self):
        N, M = map(int, input().split())
        A = list(map(int, input().split()))
        heapify(A)
        for _ in range(M):
            b, c = map(int, input().split())
            for _ in range(b):
                v = A[0]
                if v < c:
                    heappop(A)
                    heappush(A, c)
                else:
                    break
        print(sum(A))


if __name__ == '__main__':
    Solution().main()

### FIXED CODE ###

from collections import defaultdict
from heapq import heappush, heappop, heapify, heapreplace
from random import randint

class Solution:
    def main(self):
        N, M = map(int, input().split())
        A = list(map(int, input().split()))
        # A = list(range(100000))
        A = sorted(A)
        BC = []
        for _ in range(M):
            b, c = map(int, input().split())
            BC.append((b, c))
        # BC *= 100000
        BC = sorted(BC, key=lambda x: -x[1])
        idx = 0
        for i in range(M):
            # print(A)
            b, c = BC[i]
            for j in range(b):
                if idx >= N or A[idx] >= c:
                    break
                else:
                    A[idx] = c
                    idx += 1

        print(sum(A))


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

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

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    ans = 0
    for r_i in r_arr:
        for g_i in g_arr:
            for b_i in b_arr:
                tgt_list = [r_i, g_i, b_i]
                tgt_list.sort()

                if tgt_list[1] - tgt_list[0] != tgt_list[2] - tgt_list[1]:
                    ans += 1
    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing


### FIXED CODE ###

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

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    min1_arr = r_arr
    min2_arr = g_arr
    max_arr = b_arr
    if len(r_arr) < len(g_arr) and len(b_arr) < len(g_arr):
        min1_arr = r_arr
        min2_arr = b_arr
        max_arr = g_arr
    elif len(g_arr) < len(r_arr) and len(b_arr) < len(r_arr):
        min1_arr = g_arr
        min2_arr = b_arr
        max_arr = r_arr

    max_dict = dict()
    for elem in max_arr:
        max_dict[elem] = 1

    except_num = 0
    for r_i in min1_arr:
        for g_i in min2_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2

            if minmin in max_dict:
                except_num += 1
            if maxmax in max_dict:
                except_num += 1
            if exists_central == 0:
                central = (max_i + min_i) / 2
                if central in max_dict:
                    except_num += 1

    ans = len(r_arr) * len(g_arr) * len(b_arr) - except_num
    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing
### BUGGY CODE ###

from scipy.special import comb

n=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(0,n-1):
    for j in range(i+1,n):
        ans+=(A[i]%(10**9+7))*(A[j]%(10**9+7))
        ans %= 10**9+7
print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
s=0
ans=0
mod=10**9+7

for i in range(n):
    s+=A[i]

for i in range(0,n-1):
    s-=A[i]
    s%=mod
    ans+=(A[i]*s)
    ans%=mod
print(ans%(10**9+7))
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
a = [ int(i) for i in input().split() ]
ans = 0
for i in range(60):
    zero = 0
    one = 0
    if (a[n-1] & (1<<i)) == 0:
        zero += 1
    else:
        one += 1

    for j in range(n-2,-1,-1):
        if (a[j] & (1<<i)) == 0:
            ans += one * (1<<i)
            ans %= mod
            zero += 1
        else:
            ans += zero * (1<<i)
            ans %= mod
            one += 1


print(ans)                 


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [ int(i) for i in input().split() ]
ans = 0
for i in range(60):
    zero = 0
    one = 0
    if (a[n-1] & (1<<i)) == 0:
        zero += 1
    else:
        one += 1

    for j in range(n-2,-1,-1):
        if (a[j] & (1<<i)) == 0:
            ans += one * (1<<i)
            ans %= mod
            zero += 1
        else:
            ans += zero * (1<<i)
            ans %= mod
            one += 1


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

N=int(input())
S=[list(input()) for i in range(N)]
def issym(IL):
    for i in range(N):
        for j in range(i+1,N):
            if IL[i][j]!=IL[j][i]:
                return False
    return True
def changelist(A,B):
    T=[["" for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            T[i][j]=S[(i+A)%N][(j+B)%N]
    return T
ans=0
for i in range(N):
    L=changelist(i,0)
    if issym(L):
        ans+=N
print(ans)


### FIXED CODE ###

N=int(input())
S=[list(input()) for i in range(N)]
def issym(IL):
    for i in range(N):
        for j in range(i+1,N):
            if IL[i][j]!=IL[j][i]:
                return False
    return True
def changelist(A,B):
    T=[["" for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            T[i][j]=S[(i+A)%N][(j+B)%N]
    return T
ans=0
for i in range(N):
    L=changelist(i,0)
    if issym(L):
        ans+=N
print(ans)
### BUGGY CODE ###

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

dp = [-1 for _ in range(N)]

dp[0] = 0

for i in range(1, N):
    dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(1, K+1) if i-j >= 0])

print(dp[N-1])


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

# dp = np.array([-1 for _ in range(N)])
dp = np.zeros(N, dtype=int)

dp[0] = 0

for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

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

a = 0
n = int(input())
while n != 0:
  a += n % 10
  n = n // 10 

b = 0
while a != 0:
  b += a % 10
  a = a // 10 

c = 0
while b != 0:
  c += b % 10
  b = b // 10 

d = 0
while c != 0:
  d += c % 10
  c = c // 10 

e = 0
while d != 0:
  e += d % 10
  d = d // 10 


if e % 9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a = 0
s = input()
for c in s:
  a += int(c)

if a % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

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

def calc(n):
  num = {}
  e, i = 0, 2
  while n != 1:
    while n%i == 0:
      n //= i
      e += 1
    if(e > 0):
      num[i] = e
    i += 1
    e = 0
  return num

if(N == 1):
  print(P)
  exit()
elif(P == 1):
  print(1)
  exit()
else:
  cnt = 1
  for k, v in calc(P).items():
    if(v >= N):
      cnt *= k ** (v//N)
  print(cnt)

### FIXED CODE ###

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

def calc(n):
  num = {}
  e, i = 0, 2
  while i**2 <= n:
    while n%i == 0:
      n //= i
      e += 1
    if(e > 0):
      num[i] = e
    i += 1
    e = 0
  return num

if(N == 1):
  print(P)
  exit()
elif(P == 1):
  print(1)
  exit()
else:
  cnt = 1
  for k, v in calc(P).items():
    if(v >= N):
      cnt *= k ** (v//N)
  print(cnt)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
    if a>0:
        a-=1
    elif a==0 and b>0:
        b-=1
print(a,b)

### FIXED CODE ###

a,b,k=map(int,input().split())
if a-k>=0:
    print(a-k,b)
elif a+b>=k:
    print(0,a+b-k)
else:
    print(0,0)
### BUGGY CODE ###

import sys
import heapq
import bisect
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort()
ylist.sort()

hpop = heapq.heappop
hpush = heapq.heappush

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  hpush(node, [nextx - x, xID, nextxID])
  hpush(node, [nexty - y, yID, nextyID])

ans = 0
while node:
  val, i, j = hpop(node)
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
a, b, c, n = map(int, input().split())
ans = 0
for i in range(3001):
    for j in range(3001):
        if n <= i * a + j * b and (n - i * a - j * b) % c == 0:
            ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
a, b, c, n = map(int, input().split())
ans = 0
for i in range(3001):
    for j in range(3001):
        if n >= i * a + j * b and (n - i * a - j * b) % c == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(1, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            if k == 1 and K != xa:
                continue
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
INF = float('inf')
for i in range(1, N+1):
    t = -INF
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

from operator import itemgetter
import itertools
import bisect

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

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

BC = [(0, 0)]*M
for m in range(M):
    BC[m] = tuple(map(int, input().split()))
BC.sort(key=itemgetter(1), reverse = True)

def main(): 
    #print(BC)
    res = 0
    for i in range(M):
        idx = 0         
        idx = bisect.bisect_left(A, BC[i][1])
        if idx == 0:
            break
        else:
            less =min(idx, BC[i][0]) 
            del A[0:less]
            res += BC[i][1]*less

    print(res+sum(A))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019
 
@author: Owner
"""
 
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019
 
@author: Owner
"""
 
from operator import itemgetter
import itertools
import collections
import bisect
 
N, M = list(map(int, input().split()))
 
A = list(map(int, input().split()))
A.sort()

A = collections.deque(A)

BC = [(0, 0)]*M
for m in range(M):
    BC[m] = tuple(map(int, input().split()))
BC.sort(key=itemgetter(1), reverse = True)
 
def main(): 
    #print(BC)
    res = 0
    for i in range(M):
        idx = 0         
        idx = bisect.bisect_left(A, BC[i][1])
        if idx == 0:
            break
        else:
            less =min(idx, BC[i][0])
            for n in range(less):
                A.popleft()
            res += BC[i][1]*less
 
    print(res+sum(A))
                
                
                
            
            
                
 
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N,K = list(map(int, input().split()))
    p = list(map(int, input().split()))
    n = N-K+1
    kitai = [None] * n
    for i in range(N-K+1):
        kitai[i] = ((sum((p[i:i+K]))+K)*0.5)
    print('{:.12f}'.format(max(kitai)))

if __name__ == '__main__':
    main()


### FIXED CODE ###

N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
p2 = [p[i]*0.5 + 0.5 for i in range(N)]
size = N + 1
cusum = [0] * size
max = 0

for i in range(N):
    cusum[i+1] = cusum[i] + p2[i]

for i in range(N-K+1):
    tmp = cusum[i+K] - cusum[i]
    if max < tmp:
        max = tmp
print(max)
### BUGGY CODE ###


par1 , rank1 = [],[] 
par2 , rank2 = [],[]


def find(x,par,rank):
    if par[x] == x : return x
    else:
        par[x] = find(par[x],par,rank)
        return par[x]

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

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

for i in range(n): 
    par1.append(i)
    rank1.append(0)
    par2.append(i)
    rank2.append(0)

for i in range(k):
    pp,qq = map(int,input().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int,input().split())
    if (same(rr-1,ss-1,par1,rank1)) : unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par2,rank2)
    parlis.append(p1)
    if p1 in dic:
        dic[p1] += 1
    else: 
        dic[p1] = 1

ans = str(dic[parlis[0]])

for i in range(1,n):
    ans = ans + " " + str(dic[parlis[i]])

print(ans)

### FIXED CODE ###

import sys

def find(x,par,rank):
    if par[x] == x : return x
    else:
        par[x] = find(par[x],par,rank)
        return par[x]

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

n,k,l = map(int, sys.stdin.readline().split())

par1 = [i for i in range(n)]
par2 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
rank2 = [0 for i in range(n)]

for i in range(k):
    pp,qq = map(int, sys.stdin.readline().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int, sys.stdin.readline().split())
    unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par1,rank1)
    p2 = find(i,par2,rank2)
    parlis.append((p1,p2))
    if (p1,p2) in dic:
        dic[(p1,p2)] += 1
    else: 
        dic[(p1,p2)] = 1

ans =[]

for i in range(n):
    ans.append(dic[parlis[i]])

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

n = int(input())
numlist = list(map(int,input().split()))
numcount = [0]*10**6

for num in numlist:
    numcount[num] += 1
n = int(input())
anslist = []
for i in range(n):
    b,c = map(int,input().split())
    numcount[c] += numcount[b]
    numcount[b] = 0
    result = 0
    for i,num in enumerate(numcount):
        result += i*num
    anslist.append(result)

for ans in anslist:
    print(ans)


### FIXED CODE ###

n = int(input())
numlist = list(map(int,input().split()))
numcount = [0]*10**6

numset = set()
for num in numlist:
    numcount[num] += 1
    numset.add(num)
n = int(input())
anslist = []
result = 0
for num in list(numset):
    result += numcount[num]*num
    
for i in range(n):
    b,c = map(int,input().split())
    numcount[c] += numcount[b]
    result += (c-b)*numcount[b]
    anslist.append(result)

    numcount[b] = 0
    numset.add(c)
    numset.discard(b)

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

N = int(input())
A = list(map(int, input().split()))
ans = N
for i in range(N-1):
    wa = 0
    if A[i] & A[i+1] != 0:
        continue
    ans += 1
    wa = A[i] ^ A[i+1]
    for j in range(i+2, N):
        if wa & A[j] == 0:
            wa = wa ^ A[j]
            ans += 1
        else:
            break
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l,r = 0,0
ans = 0
s = 0
while l < n:
  if r < n and s+a[r] == s^a[r]:
    s += a[r]
    r += 1
    #print(s)
  else:
    ans += r-l
    s -= a[l]
    #print(s)
    l += 1

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

mod=10**9+7
def mul(a,b):
    x,y=a,b
    return (x*y)%mod

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
for i in range(K):
    #ans+=(K-i)*(((H+W)*const)%mod)+(((K-i)*i*const)%mod)*((inv*2*H*W)%mod)
    #ans%=mod
    temp1=mul(mul(H+W,const),K-i)
    ans=(ans+temp1)%mod
    temp2=mul(inv,mul(2*H*W,mul(K-i,mul(i,const))))
    ans=(ans+temp2)%mod
ans+=mul(K,mul(H+W,const))
ans%=mod
print(ans)


### FIXED CODE ###

mod=10**9+7
def mul(a,b):
    x,y=a,b
    return (x*y)%mod

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
temp1=mul(H+W,mul((K*(K+1)//2)%mod,const))
const=mul(const,inv)
u=(K*(K**2-1))//6
u%=mod
temp2=mul(2*H*W,mul(u,const))
ans=(temp1+temp2)%mod
const=mul(const,H+W-1)
ans+=mul(K,mul(H+W,const))
ans%=mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

#=====================================
class Tree():
  def __init__(self):
    self.children = set()
    self.counter = 0

  def add_child(self, child):
    self.children.add(child)
  
  def reconstruct(self, root=None):
    if root in self.children:
      self.counter += root.counter
      self.children.remove(root)
    for child in self.children:
      child.reconstruct(self)
  
  def add_count(self, x):
    self.counter += x

#=====================================
def solve():
  n,q = [int(i) for i in input().split()]
  trees = [Tree() for i in range(n)]

  for _ in range(n-1):
    a,b = [int(i) for i in input().split()]
    trees[a-1].add_child(trees[b-1])
    trees[b-1].add_child(trees[a-1])

  for _ in range(q):
    p,x = [int(i) for i in input().split()]
    trees[p-1].add_count(x)

  trees[0].reconstruct()
  
  print(*[trees[i].counter for i in range(n)])

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

### FIXED CODE ###

N, Q = map(int, input().split())
graph = [[] for i in range(200010)]
ans = [0 for i in range(200010)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)
#
readline = sys.stdin.readline


for _ in range(N - 1):
    #a, b = map(int, input().split())
    a, b = map(int, readline().split())
    a -= 1
    b -= 1

    graph[a].append(b)
    graph[b].append(a)

for _ in range(Q):
    #p, x = map(int, input().split())
    p, x = map(int, readline().split())
    p -= 1

    ans[p] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans[:N])