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

import sys
sys.setrecursionlimit(100000000)

def mult(A, B, mod): #行列A, Bの内積を求める。
    D = [[(A[0][0] * B[0][0]) % mod, 0, 0], [0, 1, 0], [0, 0, 1]]
    D[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod
    D[2][0] = (A[2][0]*B[0][0]+A[2][1]*B[1][0]+A[2][2]*B[2][0]) % mod
    D[2][1] = (A[2][1]*B[1][1]+A[2][2]*B[2][1]) % mod
    return D

def double(C, mod):
    D = [[pow(C[0][0], 2, mod), 0, 0], [(C[1][0] * C[0][0] + C[1][0]) % mod, 1, 0], [(C[2][0] * C[0][0] + C[2][1] * C[1][0] + C[2][0]) % mod, (C[2][1] * 2) % mod, 1]]
    return D

def Cpow(C, n, mod):
    if n == 1: return C
    else:
        D = double(C, mod)
        if n % 2 == 0:
            return Cpow(D, n // 2, mod)
        else:
            return mult(Cpow(D, n // 2, mod), C, mod)

def solve():
    L, a, b, M = map(int, input().split())
    X = "0"
    s = a
    nd = -1
    ne = 0
    for d in range(1, 19):
        ne = min((pow(10, d) - a - 1) // b, L-1)
        if nd == ne and ne == L - 1: break
        elif nd == ne: continue
        C = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, b % M, 1]]
        D = Cpow(C, ne - nd, M)
        X = str((int(X) * D[0][0] + D[1][0] * s + D[2][0]) % M)
        s += D[2][1]
        nd = ne
    print(X)
    return

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def mult(A, B, mod): #行列A, Bの内積を求める。
    D = [[(A[0][0] * B[0][0]) % mod, 0, 0], [0, 1, 0], [0, 0, 1]]
    D[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod
    D[2][0] = (A[2][0]*B[0][0]+A[2][1]*B[1][0]+A[2][2]*B[2][0]) % mod
    D[2][1] = (A[2][1]*B[1][1]+A[2][2]*B[2][1]) % mod
    return D

def double(C, mod):
    D = [[pow(C[0][0], 2, mod), 0, 0], [(C[1][0] * C[0][0] + C[1][0]) % mod, 1, 0], [(C[2][0] * C[0][0] + C[2][1] * C[1][0] + C[2][0]) % mod, (C[2][1] * 2) % mod, 1]]
    return D

def Cpow(C, n, mod):
    if n == 1: return C
    else:
        D = double(C, mod)
        if n % 2 == 0:
            return Cpow(D, n // 2, mod)
        else:
            return mult(Cpow(D, n // 2, mod), C, mod)

def solve():
    L, a, b, M = map(int, input().split())
    X = 0
    s = a
    nd = -1
    ne = 0
    for d in range(1, 19):
        ne = min((pow(10, d) - a - 1) // b, L-1)
        if ne < 0: continue
        elif ne == nd: continue
        C = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, b % M, 1]]
        D = Cpow(C, ne - nd, M)
        X = (X * D[0][0] + D[1][0] * s + D[2][0]) % M
        s += D[2][1]
        if ne == L - 1: break
        nd = ne
    print(X)
    return

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

import math
n,a,b = map(int,input().split())
i = 1
p = 0
if (b-a)%2==0:
    print((b-a)//2)
else:
    if a <= math.floor(n/2):
        while True:
            b -= 1
            if p == 1:
                a += 1
            elif a <= 1:
                a = 1
                p += 1
            else:
                a -= 1
            if a == b:
                print(i)
                break
            i += 1
    else:
        while True:
            a += 1
            if p == 1:
                b -= 1
            elif b >= n:
                b = n
                p += 1
            else:
                b += 1
            if a == b:
                print(i)
                break
            i += 1

### FIXED CODE ###

n,a,b = map(int,input().split())
i = 1
p = 0
if (b-a)%2==0:
    print((b-a)//2)
else:
    if a-1 < n-b:
        print(min((1+b+(a-2))//2,b-1))
    else:
        print(min((n-a+(n-b+1))//2,n-a))
### BUGGY CODE ###

#!/usr/bin/env python3

n, k = [int(i) for i in input().split(' ')]
k += 1

harr = [int(i) for i in input().split(' ')]

dp = [10**9]*n
dp[0] = 0


for i in range(1, n):
    for j in range(1, k):
        if i - j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(harr[i]-harr[i-j]))

print(dp[n-1])


### FIXED CODE ###

#!/usr/bin/env python3

n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

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

S = input()
N = len(S)
mod = 10**9 + 7

dp = [[0] * 13 for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    if S[i] == '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13] += dp[i][k] % mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(S[i]))%13] += dp[i][k] % mod
            
print(dp[-1][5] % mod)            

### FIXED CODE ###

S = input()
N = len(S)
mod = 10**9 + 7

dp = [[0] * 13 for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    if S[i] == '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13] += dp[i][k] % mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(S[i]))%13] += dp[i][k] % mod
            
print(dp[-1][5] % mod)
### BUGGY CODE ###

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

m = (n-1) // 2
s = sum(a) // 2
ans = []
for i in range(n):
    ans.append(s - sum([a[(i+1 + j*2)%n] for j in range(m)]))

print(" ".join([str(a*2) for a in ans]))


### FIXED CODE ###

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

m = (n-1) // 2
s = sum(a) // 2
x = [sum([a[(0+1 + j*2)%n] for j in range(m)]), sum([a[(1+1 + j*2)%n] for j in range(m)])]
ans = []
for i in range(n):
    index = i % 2
    ans.append(s - x[index])
    x[index] = x[index] - a[(i+1 + 0*2)%n] + a[(i+1 + m*2)%n]

print(" ".join([str(a*2) for a in ans]))
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr()
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 40)):
    next = [0] * N
    for i in range(N):
        x = A[i]
        for j in range(max(0, i-x), min(N-1, i+x)+1):
            next[j] += 1
    A = next

print(*A)

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])
### BUGGY CODE ###

import heapq,sys


def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))
    
    #A+Bでのベスト枠K個求めるO(XYlogK)
    AandB = []
    for x in A:
        for y in B:
            heapq.heappush(AandB,x+y)
            #要素がK+1個以上なら一々はじく！！！ことでO(logK)
            if len(AandB) > K:
                heapq.heappop(AandB)
    #上のとCでのベスト枠K個を求める(ZKlogK)
    heap_queue = []
    for z in C:
        for elt in AandB:
            heapq.heappush(heap_queue,z+elt)
            if len(heap_queue) > K:
                heapq.heappop(heap_queue)
    heap_queue.sort(reverse = True)
    for e in heap_queue:
        print(e)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()

ok = -1
ng = 10**12
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])
### BUGGY CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   d=0
   for i,j in enumerate(reversed(tmp)):
      d+=int(j)*10**(i)
      cnt[d%2019]+=1
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = list(input())

s_split = []
tmp = []
for i in range(len(s) - 1):
    tmp.append(s[i])
    if s[i] == 'L' and s[i + 1] == 'R':
        s_split.append(tmp)
        tmp = []
tmp.append(s[-1])
s_split.append(tmp)

out = ''
for _split in s_split:
    for i in range(len(_split) - 1):
        if _split[i] == 'R' and _split[i + 1] == 'L':
            idx = i

    if len(_split) % 2 == 0:
        r_int = len(_split) // 2
        l_int = len(_split) // 2

    else:
        if idx % 2 == 1:
            r_int = (len(_split) - 1) // 2
            l_int = (len(_split) + 1) // 2

        else:
            l_int = (len(_split) - 1) // 2
            r_int = (len(_split) + 1) // 2

    for i in range(len(_split)):
        if i < idx:
            out += ' 0'
        elif i == idx:
            out += ' ' + str(r_int)
        elif i == idx + 1:
            out += ' ' + str(l_int)
        else:
            out += ' 0'


print(out[1:])


### FIXED CODE ###

s = list(input())

s_split = []
tmp = []
idx_all = []
l = -1
for i in range(len(s) - 1):
    tmp.append(s[i])
    if s[i] == 'R' and s[i + 1] == 'L':
        idx_all.append(i - l - 1)
    if s[i] == 'L' and s[i + 1] == 'R':
        s_split.append(tmp)
        tmp = []
        l = i
tmp.append(s[-1])
s_split.append(tmp)

out = ''
for a in range(len(s_split)):
    idx = idx_all[a]
    _split = s_split[a]

    if len(_split) % 2 == 0:
        r_int = len(_split) // 2
        l_int = len(_split) // 2

    else:
        if idx % 2 == 1:
            r_int = (len(_split) - 1) // 2
            l_int = (len(_split) + 1) // 2

        else:
            l_int = (len(_split) - 1) // 2
            r_int = (len(_split) + 1) // 2

    out += ' 0' * idx
    out += ' ' + str(r_int)
    out += ' ' + str(l_int)
    out += ' 0' * (len(_split) - idx - 2)

print(out[1:])
### BUGGY CODE ###

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

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

    L0 = 2
    L1 = 1
    i = 2
    while True:
        ans = L0 + L1

        if i == N:
            break
        
        L0 = L1
        L1 = ans
        i += 1

    print(ans)

if __name__ == "__main__":
    solve()


### FIXED CODE ###

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

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

    if N == 1:
        print(1)
        return

    L0 = 2
    L1 = 1
    i = 2
    while True:
        ans = L0 + L1

        if i == N:
            break
        
        L0 = L1
        L1 = ans
        i += 1

    print(ans)

if __name__ == "__main__":
    solve()
### 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:
        if x+dx < 0 or x+dx >= H:
            continue

        if y+dy < 0 or y+dy >= W:
            continue

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

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 ###

n, k = map(int,input().split())
li = list(int(input()) for i in range(n))

li.sort()
num = 0
li2 = []
for i in range(len(li)-k+1):
    li2.append( max(li[i:i+k]) - min(li[i:i+k]))

print(min(li2))

### FIXED CODE ###

n, k = map(int,input().split())
li = list(int(input()) for i in range(n))

li.sort()
num = 0
li2 = []
for i in range(len(li)-k+1):
    li2.append(li[i+k-1] - li[i])

print(min(li2))
### BUGGY CODE ###

n,m=map(int, input().split())
h = [list(map(str,input().split())) for _ in range(m)]
# print(h)
for i in range(m):
    h[i][0] = int(h[i][0])
l=[]
penalty = 0
import numpy as np
p = np.zeros(n)
for i in range(m):
    if h[i][0] not in l:
        if h[i][1] == 'AC':
            l.append(h[i][0])
            penalty += p[h[i][0]-1]
        else:
            p[h[i][0]-1] += 1
ansnum = len(l)

# for i in l:
#     penalty += p[i-1]

print(ansnum,int(penalty))

### FIXED CODE ###

n,m=map(int, input().split())
h = [list(map(str,input().split())) for _ in range(m)]
# print(h)
for i in range(m):
    h[i][0] = int(h[i][0])
l=set()
penalty = 0
import numpy as np
p = np.zeros(n)
for i in range(m):
    if h[i][0] not in l:
        if h[i][1] == 'AC':
            l.add(h[i][0])
            penalty += p[h[i][0]-1]
        else:
            p[h[i][0]-1] += 1
ansnum = len(l)

# for i in l:
#     penalty += p[i-1]

print(ansnum,int(penalty))
### BUGGY CODE ###

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

for i in range(N):
    p[i] = (p[i]+1)/2

ans = 0
for i in range(N-K+1):
    tmp = sum(p[i:i+K])
    if tmp > ans:
        ans = tmp

print(ans)

### FIXED CODE ###

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

for i in range(N):
    p[i] = (p[i]+1)/2

ans = sum(p[:K])
tmp = ans

for i in range(N-K):
    tmp += -p[i] + p[i+K]
    if tmp > ans:
        ans = tmp

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

from fractions import gcd
mod = 10**9+7
def lcm(x, y):
  return x//gcd(x, y)*y
def main():
  n = int(input())
  A = list(map(int, input().split()))
  cnt = 0
  m = A[0]
  for i in A[1:]:
    m = lcm(m, i)
  ans = 0
  for i in A:
    ans += m//i
    ans %= mod
  print(ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

# coding :utf-8

N = int(input())

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

ans = 0
for i in range(len(A)):
    sum = A[i]
    if sum == 0:
        ans += 1
    for j in range(i+1, len(A)):
        sum += A[j]
        if sum == 0:
            ans += 1

print(ans)

### FIXED CODE ###

# coding: utf-8

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

# aの要素は1以上であるため、前方からの総和の数列sについて
# 同一の数値がでてきたとき、和が0になる連続する部分数列がある
# 例
# A = [1, 3, -4, 2, 2, -2]
# S = [1, 4, 0, 2, 4, 2]
# S_3:5 = S_5 - S_2 =(Sum(A_1:5) - Sum(A_1:2)) = 0
#


ans = 0
s = 0
# 総和順列の値について、値と個数の辞書を用意する
l ={0:1}


for i in a:
    # 数列の現在位置までの総和をカウント
    s += i
    if s in l:
        ans += l[s]
        l[s] += 1
    else:
        l[s] = 1

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

while True:
    array = []
    n, x = map(int, input().split())
    if n == x == 0:
        break
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if (i + j + k == x and i != j != k and i != j and i != k and j != k):
                    sort = sorted([i, j, k])
                    if sort not in array:
                        array.append(sorted((i, j, k)))
    print(len(array))

### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    cnt = 0
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            for k in range(j+1, n+1):
                if i + j + k == x:
                    cnt += 1
    print(cnt)
### BUGGY CODE ###

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

x=[0]
for i in range(N-1):
    if max(A[:i+1])<=A[i+1]:
        x.append(0)
    else:
        x.append(max(A[:i+1])-A[i+1])

print(sum(x))

### FIXED CODE ###

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

sum=0
MaxNum=0
for i in range(N):
    MaxNum=max(MaxNum,A[i])
    B=MaxNum
    sum+=MaxNum-A[i]
    
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)]
C = []
#"AC"が何文字目か判断
terget = "AC"
index = -1
while True:
    index = S.find(terget,index+1)
    if index == -1:
        break
    C.append(index)
    
for l,r in lr:
    AC = 0
    for j in C:
        if j >= l-1:
            if j < r-1:
                AC += 1
            else:
                break
    print(AC)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)]
C = [0]*(N+1)
terget = "AC"
index = -1
for i in range(N):
    C[i+1] = C[i] + (S[i:i+2] == "AC")
for l,r in lr:
    print(C[r-1] - C[l-1])
### BUGGY CODE ###

import math

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

c = a/b
p = []

for x in range(n + 1):
    d = math.floor(c * x) - a * math.floor(x / b)
    p.append(d)

p.sort()
print(p[n])


### FIXED CODE ###

import sys
input = sys.stdin.readline

import math

def main():
    a,b,n = map(int, input().split())

    if b > n:
        print(math.floor(a*n/b))

    else:
        print(math.floor(a*(b-1)/b) - a*math.floor((b-1)/b))

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

import sys
N = int(input())
A = list(map(int,input().split()))
AA=1
a = pow(10,18)
for i in range(N):
  AA = AA * A[i]
  if AA == 0:
    print(0)
    sys.exit()
print(AA if AA <= a else -1)

### FIXED CODE ###

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

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
G = [[-float('inf')] * N for _ in range(N)]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N

for m in range(M):
    a, b, c = [int(x) for x in input().strip().split()]
    G[a-1][b-1] = c

updated = True
updated2 = False
for n in range(N):
    updated = False
    for i in range(1, N+1):
        for j in range(1, N+1):
            if i == j:
                continue
            if G[i-1][j-1] != -float('inf') and score[j-1] < score[i-1] + G[i-1][j-1]:
                score[j-1] = score[i-1] + G[i-1][j-1]
                updated = True
                if j == N-1:
                    updated2 = True
            else:
                if j == N-1:
                    updated2 = False

if updated2:
    print('inf')
else:
    print(score[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N
edges = [0] * M
for m in range(M):
    edges[m] = tuple([int(x) for x in input().strip().split()])

for n in range(N):
    updated = False
    for (i, j, c) in edges:
        # print('i={}, j={}'.format(i, j), end='')
        if score[j-1] < score[i-1] + c:
            score[j-1] = score[i-1] + c
            if j == N-1:
                updated = True
        # print(score)
    if not updated:
        break

if updated:
    print('inf')
else:
    print(score[N-1])
### BUGGY CODE ###

S = input()

cnt = 0

for i in range(len(S)-3):
    x = int(S[i:i+3])
    for j in range(i+3, len(S)):
        x *= 10
        x += int(S[j])
        x %= 2019
        if x == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

S = list(map(int, list(input())))
S.reverse()
a = [0]*len(S)
y = 2019
x = 1
t = 0
cnt = [0]*y
res = 0
for i in range(len(S)):
    cnt[t] += 1
    t += S[i]*x
    t %= y
    res += cnt[t]
    x = x*10%y
print(res)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  for j in range(1, n - i):
    if A[i] + A[i + j] == j:
      ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

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

L = [i + a for i, a in enumerate(A)]
R = [i - a for i, a in enumerate(A)]

cL = Counter(L)
cR = Counter(R)

ans = 0
for i in cL.keys():
  ans += cL[i] * cR[i]

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

H, W = map(int, input().split())
s = [list(input()) for x in range(H)]
d = [[None for y in range(W)] for x in range(H)]
q = []
white = 0
for x in range(H):
  for y in range(W):
    if s[x][y] == '.':
      white += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append([0, 0, 0])

def Haba(x_now, y_now, d_now, s, d, q):
  s[x_now][y_now] = '#'
  d[x_now][y_now] = d_now
  for i in range(4):
    if 0 <= x_now + dx[i] and x_now + dx[i] < H and 0 <= y_now + dy[i] and y_now + dy[i] < W:
      if s[x_now + dx[i]][y_now + dy[i]] == '.':
        q.append([x_now+dx[i], y_now+dy[i], d_now + 1])
while(len(q) != 0):
  x_now, y_now, d_now = q.pop(0)
  Haba(x_now, y_now, d_now, s, d, q)
if d[H - 1][W - 1] is not None:
  ans = white - d[H - 1][W - 1]  - 1
else:
  ans = -1
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
s = [list(input()) for x in range(H)]
d = [[None for y in range(W)] for x in range(H)]
q = []
white = 0
for x in range(H):
  for y in range(W):
    if s[x][y] == '.':
      white += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append([0, 0, 0])

def Haba(x_now, y_now, d_now, s, d, q):
  for i in range(4):
    if 0 <= x_now + dx[i] and x_now + dx[i] < H and 0 <= y_now + dy[i] and y_now + dy[i] < W:
      if s[x_now + dx[i]][y_now + dy[i]] == '.':
        s[x_now + dx[i]][y_now + dy[i]] = '#'
        d[x_now + dx[i]][y_now + dy[i]] = d_now + 1
        q.append([x_now+dx[i], y_now+dy[i], d_now + 1])

while(len(q) > 0):
  x_now, y_now, d_now = q.pop(0)
  Haba(x_now, y_now, d_now, s, d, q)
if d[H - 1][W - 1] is not None:
  ans = white - d[H - 1][W - 1]  - 1
else:
  ans = -1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split(" "))

ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]
dic = dict.fromkeys(range(1,N+1), 1)
rlt = dict.fromkeys(range(1,N+1), 0)
for i in range(N-1):
  dic[ns[i][1]] = ns[i][0]
  
for q in vs:
  rlt[q[0]] = rlt[q[0]] + q[1]
  l = [i for i in range(q[0]+1,N+1) if dic[i] == q[0]]
  while len(l) > 0:
    t = l.pop(0)
    rlt[t] = rlt[t] + q[1]
    l1 = [i for i in range(t+1,N+1) if dic[i] == t]
    l.extend(l1)
    
print(" ".join(map(str, list(rlt.values()))))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]

dic = [[] for _ in range(N)]
rlt = [0]*N


for i in range(N-1):
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for j in range(Q):
  rlt[vs[j][0]-1] += vs[j][1]
  
for k in range(N):
  for l in dic[k]:
    rlt[l] += rlt[k]
    
print(" ".join(map(str, rlt)))