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

import math
import decimal

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

ans=[]

for i in range(1,n+1):
  x=decimal.Decimal(a*i/b)
  y=decimal.Decimal(i/b)
  c=math.floor(x)-a*math.floor(y)
  ans.append(c)

print(max(ans))

### FIXED CODE ###

import math
import decimal

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

if b<=n:
  x=decimal.Decimal(a*(b-1)/b)
  c=math.floor(x)
  print(c)

else:
  x=decimal.Decimal(a*n/b)
  c=math.floor(x)
  print(c)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

# エラトステネスの篩
#############################################################
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
#############################################################

# 素因数分解、リストで返す
#############################################################
def prime_factorize(n, prime_list):
    a = []
    for p in prime_list:
        while p * p <= n:
            if n % p == 0:
                a.append(p)
                n //= p
            else:
                break
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# 素因数分解、リストで返す
#############################################################


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Aug 18 21:19:43 2019
ABC138D
@author: maezawa
"""

n, q = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    graph[ai].append(bi)
    graph[bi].append(ai)
    
parent = [[] for _ in range(n+1)]
child = [[] for _ in range(n+1)]
current = 1
while current <= n:
    for j in graph[current]:
        if current in child[j]:
            continue
        child[current].append(j)
    current += 1
#print(child)
parray = [-1]*(n+1)
parray[1] = 0
for i in range(1,n+1):
    for j in child[i]:
        parray[j] = i
#print(parray)
tpoint = [0]*(n+1)
for i in range(q):
    pi, xi = list(map(int, input().split()))
    tpoint[pi] += xi
tpmem = [-1]*(n+1)
for i in range(1, n+1):
    pi = 0
    j = i
    while True:
        if tpmem[j] != -1:
            pi += tpmem[j]
            break
        pi += tpoint[j]
        if parray[j] == -1:
            break
        j = parray[j]
    print(pi)
    tpmem[i] = pi
    

### FIXED CODE ###

n, q = list(map(int, input().split()))
nodes = [[] for _ in range(n)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    nodes[ai-1].append(bi-1)
    nodes[bi-1].append(ai-1)
    
cnts = [0]*n
for _ in range(q):
    pi, xi = list(map(int, input().split()))
    cnts[pi-1] += xi
    
stack = []
visited = set()
stack.append(0)
while stack:
    current = stack.pop(-1)
    visited.add(current)
    for j in nodes[current]:
        if j in visited:
            continue
        cnts[j] += cnts[current]
        stack.append(j)
        
print(*cnts)
### BUGGY CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        s.add(x)
        ro = R[x]
        for i in ro:
            if r[i] == 0 and i not in s and i not in q:
                r[i] = x
                q.append(i)
    if len(s) == N:
        print("Yes")
        print("\n".join(map(str, r[2:])))
    else:
        print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    #s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        #s.add(x)
        ro = R[x]
        for i in ro:
            #if r[i] == 0 and i not in s and i not in q:
            if r[i] == 0: 
                r[i] = x
                q.append(i)
    #if len(s) == N:
    print("Yes")
    print("\n".join(map(str, r[2:])))
    #else:
    #    print("No")

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

n, k = map(int, input().split())
s = input()
one = [i.count('1') for i in s.split('0') if i.count('1') > 0]
zero = [i.count('0') for i in s.split('1') if i.count('0') > 0]
if s[0] == '1':
    nums = sum([[i, j] for i, j in zip(one,zero)], [])
    if s[-1] == '1':
        nums.append(one[-1])
    a = sum(nums[:k*2+1])
    rslt = a
    for i in range(k*2+1,len(nums), 2):
        a += sum(nums[i:i+2])
        a -= sum(nums[i-2*k-1:i-2*k+1])        
        rslt = max(rslt, a)
else:
    nums = sum([[i, j] for i, j in zip(zero,one)], [])
    if s[-1] == '0':
        nums.append(zero[-1])
    a = sum(nums[:k*2])
    rslt = a
    for i in range(k*2, len(nums), 2):
        a += sum(nums[i:i+2])
        a -= sum(nums[max(0,i-2*k-1):i-2*k+1])
        rslt = max(rslt, a)
print(rslt)

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
l = []
c = 1
for i in range(n - 1):
    if s[i] != s[i + 1]:
        l.append(c)
        c = 0
    c += 1
l.append(c)
l += [0]
if s[0] == '0':
    l = [0] + l
tmp = sum(l[:2 * k + 1])
rslt = tmp
for i in range(0, len(l) - 2*k-2, 2):
    tmp = tmp - l[i] - l[i + 1] + l[i + 2 * k + 1] + l[i + 2 * k + 2]
    rslt = max(tmp, rslt)
print(rslt)
### BUGGY CODE ###

S = list(input().strip())
length = len(S)
check = ""
for i in range(length):
    check += S[i]

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += S[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
checkValue()
    
def dfs(total, i, j, group):
    if (len(group) != 0 and int(group) % 2019 == 0):
        print(i, j, group)
        return 1
    if i > j:
        return 0
    if (i > length-1 or j > length-1):
        return 0
    if len(group) != 0 and int(group) > int(check):
        return 0    
    return dfs(total, i+1, j, group+S[i]) + dfs(total, i, j+1, group+S[j])

#print(dfs(0, 0, 0, ""))


### FIXED CODE ###

import numpy as np
#S = list(input().strip())
#length = len(S)
#op = np.asarray(S)

def solution():
    S = input()
    N = len(S)
    num = [0] * 2019
    num[0] = 1
    c, ans, dgt = 0, 0, 1
    for i in range(N-1, -1, -1):
        c = (c + int(S[i]) * dgt) % 2019
        dgt *= 10
        dgt %= 2019
        ans += num[c]
        num[c] += 1
        
    print(ans)

solution()



def sample():
    x = -1
    count = 0
    for i in op:
        x += 1
        group = ""
        for j, name in enumerate(op, x):
            group += name
            if int(group) % 2019 == 0:
                count += 1
    print(count)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
#checkValue()
### BUGGY CODE ###

import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
import bisect


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    # M = [L[i] + L[j] for i in range(N) for j in range(i+1, N)]
    # M.sort()

    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            a = L[i]
            b = L[j]

            # l = bisect.bisect_right(L[j+1:], abs(a-b))
            l = 0
            # print(l)

            # Speed up
            if L[j+1] > a + b:
                r = -1
            elif L[-1] < a + b:
                r = len(L[j+1:]) - 1
            else:
                r = bisect.bisect_left(L[j+1:], a+b)-1
            # candidates: [l, r]

            ans += max(0, r - l + 1)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
from bisect import bisect


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    # M = [L[i] + L[j] for i in range(N) for j in range(i+1, N)]
    # M.sort()

    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):

            ans += bisect(L,L[i]+L[j]-1)-j-1

    print(ans)


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

n,m = map(int,input().split())
matrix = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    matrix[a].append(b)
    matrix[b].append(a)
for i in matrix[0]:
    if i in matrix[n-1]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
Check1 = [False]*n
Check2 = [False]*n
for i in range(m):
    a,b = map(int,input().split())
    if a ==1:
        Check1[b-1] = True
    elif a == n:
        Check2[b-1] = True
    elif b == 1:
        Check1[a-1] = True
    elif b == n:
        Check2[a-1] = True
for i in range(n):
    if Check1[i] and Check2[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
s = input()
dp = [[0 for i in range(n+1)] for j in range(n+1)]
ans = 0
for i in range(n):
  for j in range(n):
    if i == j:
      break
    if s[i] == s[j]:
      t = dp[i][j]
      if j == i-t:
        dp[i+1][j+1]=1
      else:
        dp[i+1][j+1]=1+t
        ans = max(ans, 1+t)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
dp = [[0 for i in range(n+1)] for j in range(n+1)]
ans = 0
for i in range(n):
  for j in range(n):
    if i == j:
      break
    if s[i] == s[j]:
      t = dp[i][j]
      if j == i-t:
        dp[i+1][j+1]=1
      else:
        dp[i+1][j+1]=1+t
        ans = max(ans, 1+t)

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bclist = [[0] for i in range(q)]
ans = []

for i in range(q):
    count = 0
    b, c = map(int, input().split())

    for j in a:
        if j == b:
            a[count] = c
        count += 1
    a_list = [_ for _ in a]
    ans.append(a_list)

for answer in ans:
    print(sum(answer))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
x = [0] * 100001
ans = sum(a)

for ai in a:
    x[ai] += 1  # xのなかでaiが登場する個数のカウント

for _ in range(q):
    b, c = map(int, input().split())
    ans += (c-b) * x[b]
    x[c] += x[b]  # bをcに入れ替えた個数だけcが増加する
    x[b] = 0
    print(ans)

# for i in range(q):
#     count = 0
#     b, c = map(int, input().split())
#
#     for j in a:
#         if j == b:
#             a[count] = c
#         count += 1
#     a_list = [_ for _ in a]
#     ans.append(a_list)
#
# for answer in ans:
#     print(sum(answer))
### BUGGY CODE ###

def z(x,y,N):
    if x > y:
        return(x-y)
    else:
        return(y-x)
N,X,Y = map(int,input().split())
X -= 1
Y -= 1
A = [0] * N
for i in range(N):
    for j in range(i+1,N):
        a = min([z(i,j,N),z(i,Y,N) + 1 + z(X,j,N),z(i,X,N) + 1 + z(Y,j,N)])
        A[a] += 1
for i in range(N-1):
    print(A[i+1])

### FIXED CODE ###

def z(x,y):
    if x > y:
        return(x-y)
    else:
        return(y-x)
N,X,Y = map(int,input().split())
X -= 1
Y -= 1
A = [0] * N
for i in range(N):
    for j in range(i+1,N):
        a = min(j-i,z(i,X) + 1 + z(j,Y))
        A[a] += 1
for i in range(N-1):
    print(A[i+1])
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))
 
ans4 = list()
for i in range(n - (k-1)):
    ans4.append(sum(P[i:i+k]))
 
am = np.argmax(ans4)
am2 = P[am:am+k]
ans = 0
for i in am2:
    for j in range(1, i + 1):
        ans += j / i
print(ans)

### FIXED CODE ###

from itertools import accumulate

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

# 期待値の前計算
expP = [(P[i]+1)/2 for i in range(n)]

# 累積和の計算
acc = [0]+ list(accumulate(expP)) # 0を忘れずに

# 隣接する K 項の和の計算
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

def nyu():
    N, M = map(int, input().split())
    X = list(map(int,input().split()))
    X.sort()
    return N,M,X


def kansu(N,M,X):

    x_abs = [X[m+1] -X[m] for m in range(M-1)]    
#    print(x_abs)
    cnt_n = N
    
    while cnt_n-1 > 0:
        x_abs[x_abs.index(max(x_abs))]  = -1
        cnt_n -= 1

    koma_max = 0
    sum = 0
    for m in range(M-1):
        if x_abs[m] != -1:
            koma_max += x_abs[m]

    print(koma_max)

 


N,M,X = nyu()
#print(X)

if M == 1:
    print(0)
else:
    kansu(N,M,X)

#print(S)



### FIXED CODE ###

def nyu():
    N, M = map(int, input().split())
    X = list(map(int,input().split()))
    X.sort()
    return N,M,X


def kansu(N,M,X):

    x_abs = [X[m+1] -X[m] for m in range(M-1)]    
#    print(x_abs)

    
    x_abs.sort()

    koma_max = 0
    for m in range(M-N):
        koma_max += x_abs[m]

    print(koma_max)


N,M,X = nyu()
#print(X)

if M == 1:
    print(0)
else:
    kansu(N,M,X)

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

import sys
*data, = map(int, sys.stdin.read().split()[::-1])
def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])


mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        for level in range(4):
            dp[0][row][col] = max(dp[0][row][col], dp[level][row - 1][col])
            dp[1][row][col] = max(dp[1][row][col], dp[level][row - 1][col] + grid[row - 1][col - 1])
        for level in range(1, 4):
            dp[level][row][col] = max(
                dp[level][row][col],
                dp[level - 1][row][col - 1] + grid[row - 1][col - 1],
                dp[level][row][col - 1],
            )
            mx = max(mx, dp[level][row][col])

print(mx)


### FIXED CODE ###

import sys
import time
s1 = time.time()
*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])

# print(time.time() - s1)
mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        level = 0
        dp[1][row][col] = max(dp[1][row][col], dp[3][row - 1][col] + grid[row - 1][col - 1])
        dp[0][row][col] = max(dp[0][row][col], dp[3][row - 1][col])
        level = 1
        v = grid[row - 1][col - 1]
        while level < 4:
            dp[level][row][col] = max(
                dp[level - 1][row][col],
                dp[level][row][col],
                dp[level][row][col - 1],
                dp[level - 1][row][col - 1] + v,
            )
            mx = max(mx, dp[level][row][col])
            level += 1

# print(time.time() - s1)
print(mx)
### BUGGY CODE ###

#!/user/bin/env python
#pythonプログラムであることを示している

# -*- coding: utf-8 -*-
"""
このプログラムはPythonを書く際のテンプレとなっています。これをコピペしてコーディングを行なってください。
なお字下げしないこと！！
"""

__author_ = 'Maruta Yuzuha'
__version_ = '1.0.0'
__date__ = '2019/12/25'

def main():
    """
    ここでプログラムの解説を行う
     >>main()
    Hello world.
    0
    """
    s = input().split()
    t = input().split()
    for i in range(int(s[0])):
        t[i] = int(t[i])
    a = 0  #勝つまでの回数
    # c = sum(t)
    # d = int(s[1])
    # for i in range(int(s[1])):
    #     if sum(t) != 0:
    #         if d != 0:
    #             c -= max(t)
    #             for j in range(int(s[0])):
    #                 if max(t) == t[j]:
    #                     t[j] = 0
    #             d -= 1
    #         else:
    #             break
    e = 0  #Max
    f = 0# Maxのいち
    for j in range(int(s[1])):  #必殺技の回数
        c = sum(t)
        if c != 0:
            for i in range(int(s[0])):
                if e < t[i]:
                    e = t[i]
                    f = i
            t[f] = 0
            e = 0
            f = 0
        else:
            break
    a += sum(t)
    print(a)
    return 0

if __name__ == '__main__':
    #上記のifの記述によってこのスクリプトファイルが起動された時だけ実行する部分になる。
    #ちなみにスクリプトが "モジュールとして"インポートされた時には実行されない、

    #単体テスト:モジュールのdocstring(ドキュメンテーション文字列)に記載された全ての対話実行例が書かれている通りに動作するかを確認
    #python ファイル名 -v
    import doctest
    doctest.testmod()

    #実際にmain()を呼び出して、結果を得て、その結果でPythonシステムを終える
    import sys
    sys.exit(main())

### FIXED CODE ###

#!/user/bin/env python
#pythonプログラムであることを示している

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

def main():
    """
    ここでプログラムの解説を行う
     >>main()
    Hello world.
    0
    """
    s = list(map(int, input().split()))
    t = list(map(int, input().split()))
    t.sort(reverse=True)
    a = 0  #勝つまでの回数
    b = s[0]#何匹か
    d = s[1]#必殺技の回数
    f = 0# Maxのいち
    # for j in range(d):  #必殺技の回数
    #     c = sum(t)
    #     if c != 0:
    #         g = max(t)
    #         for i in range(b):
    #             if g == t[i]:
    #                 t[i] = 0
    #                 break
    #         t[f] = 0
    #         f = 0
    #     else:
    #         break
    c = sum(t)
    for i in range(d):
        if c != 0:
            c -= t[i]
            t[i] = 0
        else:
            break
    a += sum(t)
    print(a)
    return 0

if __name__ == '__main__':

    #実際にmain()を呼び出して、結果を得て、その結果でPythonシステムを終える
    import sys
    sys.exit(main())
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0

for i in range(N):
  if S[i]=='R':
    for j in range(i+1,N):
      if S[j]=='G':
        ans += S[j+1:].count('B')
        if 2*j-i<=N-1 and S[2*j-i]=='B':
          ans -= 1
      if S[j]=='B':
        ans += S[j+1:].count('G')
        if 2*j-i<=N-1 and S[2*j-i]=='G':
          ans -= 1
  if S[i]=='G':
    for j in range(i+1,N):
      if S[j]=='R':
        ans += S[j+1:].count('B')
        if 2*j-i<=N-1 and S[2*j-i]=='B':
          ans -= 1
      if S[j]=='B':
        ans += S[j+1:].count('R')
        if 2*j-i<=N-1 and S[2*j-i]=='R':
          ans -= 1
  if S[i]=='B':
    for j in range(i+1,N):
      if S[j]=='G':
        ans += S[j+1:].count('R')
        if 2*j-i<=N-1 and S[2*j-i]=='R':
          ans -= 1
      if S[j]=='R':
        ans += S[j+1:].count('G')
        if 2*j-i<=N-1 and S[2*j-i]=='G':
          ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

for i in range(N):
  for j in range(i+1,N):
    k=2*j-i
    if k<N and S[i]!=S[j]!=S[k]!=S[i]:
      ans -= 1

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

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        else:
            if j != 0:
                a[i].append(k)
                al[i].append(j-1)
                k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        else:
            if j != 0:
                b[i].append(k)
                bl[i].append(j-1)
                k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][bisect_left(al[i], j)]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)

print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
nodes = [0]*(N+1)
tree = [set() for _ in range(N+1)]
subtree = [set() for _ in range(N+1)]

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].add(b)

def add(p, x):
  dq = deque()
  dq.append(p)
  subtree[p] = {p}
  while len(dq) > 0:
    tp = dq.popleft()
    nodes[tp] += x
    for np in tree[tp]:
      dq.append(np)
      subtree[p].add(np)

for i in range(Q):
  p, x = map(int, input().split())
  if subtree[p]:
    for j in subtree[p]:
      nodes[j] += x
  else:
    add(p, x)
print(" ".join([str(i) for i in nodes[1:]]))

### FIXED CODE ###

N, Q = map(int, input().split())
tree = [[] for i in range(N)]

for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].extend([b])

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

for i in range(N-1):
  for j in tree[i]:
    nodes[j-1]+=nodes[i]
print(" ".join(list(map(str, nodes))))