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

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

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

m = [list(map(lambda x: 1 if x=="#" else 0, input())) for _ in range(H)]
black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]

# print(m)
# print(black)

queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue_append((next_p[0], next_p[1], ans+1))
print(ans)


### FIXED CODE ###

from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

inp = input()

s = 0

for i in range(len(inp)-3):
	num = int(inp[i:])
	while num > 2019:
		if num % 2019 == 0:
			s += 1
			num = num // 10
		elif num % 2019 < 10:
			num = num // 10
		elif num % 2019 < 100:
			num = num // 100
		elif num % 2019 < 1000:
			num = num // 1000
		else:
			num = num // 10000
print(s)

### FIXED CODE ###

from collections import defaultdict

s = input()

rests = [0]
n = 0
a = 0
m = 1
c = defaultdict(int)
c[0] += 1
for i in list(s)[::-1]:
    n = n + int(i)*m

    c[n % 2019] += 1
    m = m * 10 % 2019

for v in c.values():
    a += v * (v-1) // 2
print(a)
### BUGGY CODE ###

def i_coins(N, P):
    """
    N枚の番号が振られたコインがある。i番目のコインを投げたときに
    表が出る確率はp_i, 裏が出る確率は1-p_iである。
    N枚のコインをすべて投げるとき、表の枚数が裏の枚数を上回る確率を求めよ。
    """
    # dp[i][j]: コインをi枚使ったとき、表がj枚である確率
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0  # これで初期化(0枚投げて表が0枚である確率は考えられないが)
    for i in range(1, N + 1):
        # 表が出た回数が投げたコインの枚数を上回ることはありえない
        for j in range(i + 1):
            # i枚使ってj枚表が出る確率
            # = i-1枚使ってj-1枚表が出る確率 * i枚目が表である確率
            # + i-1枚使ってj枚表が出る確率 * i枚目が裏である確率
            dp[i][j] = (dp[i - 1][j - 1] * P[i - 1] * int(j >= 1)
                        + dp[i - 1][j] * (1.0 - P[i - 1]))

    ans = 0.0
    for i in range(N // 2 + 1, N + 1):
        ans += dp[N][i]  # N枚使ってN//2+1枚以上表が出る確率を足し合わせると解
    ans = round(ans, 11)  # round()は正確には偶数への丸めだが、使う
    return ans

N = int(input())
P = [float(i) for i in input().split()]
print(i_coins(N, P))

### FIXED CODE ###

def i_coins(N, P):
    """
    N枚の番号が振られたコインがある。i番目のコインを投げたときに
    表が出る確率はp_i, 裏が出る確率は1-p_iである。
    N枚のコインをすべて投げるとき、表の枚数が裏の枚数を上回る確率を求めよ。
    """
    # dp[i][j]: コインをi枚使ったとき、表がj枚である確率
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0  # これで初期化(0枚投げて表が0枚である確率は考えられないが)
    for i in range(1, N + 1):
        # 表が出た回数が投げたコインの枚数を上回ることはありえない
        for j in range(i + 1):
            # i枚使ってj枚表が出る確率
            # = i-1枚使ってj-1枚表が出る確率 * i枚目が表である確率
            # + i-1枚使ってj枚表が出る確率 * i枚目が裏である確率
            dp[i][j] = (dp[i - 1][j - 1] * P[i - 1] * int(j >= 1)
                        + dp[i - 1][j] * (1.0 - P[i - 1]))

    ans = 0.0
    for i in range(N // 2 + 1, N + 1):
        ans += dp[N][i]  # N枚使ってN//2+1枚以上表が出る確率を足し合わせると解
    ans = round(ans, 11)  # round()は正確には偶数への丸めだが、使う
    return ans

N = int(input())
P = [float(i) for i in input().split()]
print(i_coins(N, P))
### BUGGY CODE ###

while True:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    state=[raw_input().split() for i in range(r)]
    state=map(list,zip(*state))
    new_state=[int("".join(ls),2) for ls in state]
    ans=0
    h=r/2
    for i in range(pow(2,r)):
        cnt=0
        for j in new_state:
            b=format(i^j,"b")
            n=b.count("1")
            cnt+=n if n>h else r-n
        ans=max(ans,cnt)
    print ans

### FIXED CODE ###

while True:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    state=[raw_input().split() for i in range(r)]
    state=map(list,zip(*state))
    new_state=[int("".join(ls),2) for ls in state]
    ans=0
    h=r/2
    for i in range(pow(2,r)):
        cnt=0
        for j in new_state:
            n=bin(i^j).count("1")
            cnt+=n if n>h else r-n
        ans=max(ans,cnt)
    print ans
### BUGGY CODE ###

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

mod = 10**9+7

mm0 = [0 for i in range(60)]
mm1 = [0 for i in range(60)]

for i in range(n):
    for j in range(60):
        if (a[i]>>j)<0:
            break
        if (a[i]>>j)&1:
            mm1[j] += 1

ans = 0
for i in range(60):
    ttl = ((n-mm1[i])*mm1[i])
    ans += ((1<<i)%mod)*((ttl)%mod)
    ans %= mod

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
mod = 10**9+7
 
 
 
ans = 0
q2 = 1
for j in range(60):
    mm1 = 0
    for i in range(n):
        if a[i]>>j&1:
            mm1 += 1
 
    ttl = ((n-mm1)*mm1)
    ans += ((q2)*((ttl)%mod))%mod
    ans %= mod
    q2 = (q2*2)%mod
 
print(ans)
### BUGGY CODE ###

import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
Q = int(input())
b = [input().split() for l in range(Q)]
a = np.array(a)
b = np.array(b)
a = np.int64(a)
b = np.int64(b)
ans = []
memo = {}
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  if (str(syo)+ " " + str(go)) in memo:
    ans.append(memo[str(syo)+ " " + str(go)])
    continue
  syouhi = 0
  while syo != go:
    c = np.where(a == syo)
    syo += D
    d = np.where(a == syo)
    syouhi += abs(c[0][0] - d[0][0]) + abs(c[1][0] - d[1][0])
  ans.append(syouhi)
  memo[str(syo)+ " " + str(go)] = syouhi
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
basyo = [[0,0] for i in range(H*W)]
for i in range(W):
  for j in range(H):
    basyo[int(a[j][i])-1] = [j,i]
Q = int(input())
b = [input().split() for l in range(Q)]
ans = []
memo = [0] * (H*W+1)
for i in range(D):
  while i < H*W:
    i += D
    if i >= H*W:
      break
    memo[i] = memo[i-D]  + abs(basyo[i][0] - basyo[i-D][0]) + abs(basyo[i-D][1] - basyo[i][1])
b = np.array(b)
b = np.int64(b)
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  print(memo[go-1] - memo[syo-1])
### BUGGY CODE ###

if __name__ == '__main__':
    import sys
    
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    
    set_a = set(A)
    
    num_dic = {}
    comb_dic = {}
    comb_dic_ex = {}
    comb_sum = 0
    
    for i in set_a:
        num_dic[i] = A.count(i)
        n = num_dic[i]
        if num_dic[i] == 1:
            comb_dic[i] = 0
            comb_dic_ex[i] = 0
        else:
            comb_dic[i] = n * (n - 1) / 2
            comb_dic_ex[i] = (n - 1) * (n - 2) / 2
        comb_sum += comb_dic[i]
     
    for j in range(N):
        n = A[j]
        ans = int(comb_dic_ex[n] + comb_sum - comb_dic[n])
        print(ans)

### FIXED CODE ###

def main():
    import sys
    from collections import Counter
    
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    
    count = Counter(A)
    
    d = {}
    comb_sum = 0
    
    for i, n in count.items():
        if n == 1:
            comb = 0
            comb_ex = 0
        else:
            comb = n * (n - 1) / 2
            comb_ex = (n - 1) * (n - 2) / 2
        comb_sum += comb
        d[i] = comb_ex - comb
     
    for n in A:
        ans = int(d[n] + comb_sum)
        print(ans)

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

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

G = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

dist = [-1] * (N + 1)

dist[1] = 0
q = [1]
while q.__len__():
    now = q.pop(0)
    for i in G[now]:
        if dist[i] == -1:
            q.append(i)
            dist[i] = now

print("Yes")
for i in range(2, N + 1):
    print(dist[i])

### FIXED CODE ###

import sys

input = sys.stdin.readline
from collections import *


def bfs():
    q = deque([1])
    dist = [0] * (N + 1)
    while q:
        v = q.popleft()

        for nv in G[v]:
            if dist[nv] == 0:
                dist[nv] = v
                q.append(nv)

    return dist


N, M = map(int, input().split())
G = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

dist = bfs()

print("Yes")
for i in range(2, N + 1):
    print(dist[i])
### BUGGY CODE ###

def chk(A,B):
  nL=len(A)
  if A[0]==B[0]:
    if nL==1:
      return 1
    else:
      return chk(A[1:],B[1:])
  else:
    return 0
n=int(input())
s=[sorted(input()) for i in range(n)]
s.sort()
cnt=0
k=0
for i in range(n-1):
  for j in range(i+1,n):
    k=chk(s[i],s[j])
    if k==0:
      break
    else:
      cnt+=k
print(cnt)

### FIXED CODE ###

n=int(input())
A={}
for i in range(n):
  s=str(sorted(input()))
  if s in A.keys():
    A[s]+=1
  else:
    A[s]=1
ans=0
for i in list(A.values()):
  ans+=int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
S = [[N]*N for _ in range(N)]

for i in range(N):
    S[i][i] = 0

    if i != N-1:
        S[i][i+1] = 1
        S[i+1][i] = 1

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
                S[i][j] = min(S[i][j], S[i][k]+S[k][j])
        #for k in [X-1, Y-1]:
            #S[i][j] = min(S[i][j], S[i][k]+S[k][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])

### FIXED CODE ###

N, X, Y = map(int, input().split())
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    n, m = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    h = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    # matrix = [[0 for i in range(n)] for j in range(n)]
    matrix = {}

    for i in range(m):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
        a, b = a-1, b-1
        # matrix[a][b] = 1
        # matrix[b][a] = 1
        matrix[a] = matrix.get(a, []) + [b]
        matrix[b] = matrix.get(b, []) + [a]

    good = 0
    # 展望台iが良い展望台か
    for i in range(n):
        # for j in range(n):
        #     # if matrix[i][j] == 1 and h[i] <= h[j]:
        #     if matrix.get(i*n+j, 0) == 1 and h[i] <= h[j]:
        #         break
        for t in matrix.get(i, []):
            if h[i] <= h[t]:
                break
        else:
            good += 1
    print(good)

# matrixを疎行列にする
# 判定順をソートする


### FIXED CODE ###

import sys

if __name__ == '__main__':
    n, m = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    h = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    # matrix = {}
    # matrix = [[0 for i in range(n)] for j in range(n)]
    matrix = [[] for j in range(n)]

    for i in range(m):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
        a, b = a-1, b-1
        # matrix[a] = matrix.get(a, []) + [b]
        # matrix[b] = matrix.get(b, []) + [a]
        # matrix[a][b] = 1
        # matrix[b][a] = 1
        matrix[a].append(b)
        matrix[b].append(a)

    bads = {}
    good = 0
    # 展望台iが良い展望台か
    for i in range(n):
        if bads.get(i, 0) == 1:
            continue
        # for t in matrix.get(i, []):
        for t in matrix[i]:
            if h[i] <= h[t]:
                break
            else:
                # 展望台tはもはや良い展望台でない
                if t > i:
                    bads[t] = 1
        else:
            good += 1
    print(good)

# matrixを疎行列にする
# 判定順をソートする
### BUGGY CODE ###

n = int(input())
s = input()
min = s.count('#')
if s.count('.')  < min:
  min = s.count('.') 
for i in range(len(s)-1):
  if s[:i].count('#') + s[i+1:].count('.')  < min:
    min = s[:i].count('#') + s[i+1:].count('.')
print(min)

### FIXED CODE ###

n = int(input())
s = input()
cost = s.count('.')
min = cost
for i in range(len(s)):
  if s[i]  == '.':
  	cost -= 1
  else:
    cost += 1
  if cost < min:
    min = cost
print(min)
### BUGGY CODE ###

h,w,m=map(int,input().split())
g=[]
e1=[0]*h
e2=[0]*w
for c in range(m):
    a,b=map(int,input().split())
    g.append([a-1,b-1])
    e1[a-1]+=1
    e2[b-1]+=1
p1=max(e1)
p2=max(e2)
x=[c for c in range(h) if e1[c]==p1]
y=[c for c in range(w) if e2[c]==p2]
if len(x)*len(y)>m:
    print(p1+p2)
    exit()
for i in x:
    for j in y:
        if [i,j] not in g:
            print(p1+p2)
            exit()
print(p1+p2-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
g=[]
e1=[0]*h
e2=[0]*w
for c in range(m):
    a,b=map(int,input().split())
    g.append([a-1,b-1])
    e1[a-1]+=1
    e2[b-1]+=1
p1=max(e1)
p2=max(e2)
x=[1 if e1[c]==p1 else 0 for c in range(h)]
y=[1 if e2[c]==p2 else 0 for c in range(w)]
r=sum(x)*sum(y)
for i in g:
    if x[i[0]]==1 and y[i[1]]==1:
        r-=1
if r==0:
    print(p1+p2-1)
else:
    print(p1+p2)
### BUGGY CODE ###

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

L=[0]*1000
D={}

for i in range(N-2):
    for j in range(i+1,N-1):
        s=str(S[i])+str(S[j])
        if(D.get(int(s),None)==None):
            D[int(s)]=1
            for k in range(j+1,N):
                t=str(S[i])+str(S[j])+str(S[k])
                L[int(t)]=1
print(sum(L))



### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for a in range(10):
  for b in range(10):
    for c in range(10):
      a, b, c = str(a), str(b), str(c)
      a_find = s.find(a)
      if a_find == -1:
        continue
      b_find = s.find(b, a_find + 1)
      if b_find == -1:
        continue
      c_find = s.find(c, b_find + 1)
      if c_find == -1:
        continue
      ans += 1
print(ans)
### BUGGY CODE ###

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

for i in range(k):
    if (a >= 1):
        a -= 1
    elif (b >= 1):
        b -= 1
print("{} {}".format(a, b))


### FIXED CODE ###

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

"""
for i in range(k):
    if (a >= 1):
        a -= 1
    elif (b >= 1):
        b -= 1
print("{} {}".format(a, b))
"""

if (a > k):
    ax = a - k
    bx = b
else:
    ax = 0
    bx = max(a+b-k, 0)

print("{} {}".format(ax, bx))
### BUGGY CODE ###

import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
root = 1
queue = deque([root])
color_v = [[] for _ in range(N + 1)]

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        while number in color_v[V]:
            number += 1
        color[v] = number
        color_v[V].append(number)
        color_v[v].append(number)
        queue.append(v)

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

### FIXED CODE ###

import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
queue = deque([1])
color_v = [set() for _ in range(N + 1)]

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number in color_v[V]:
            number += 1
        color[v] = number
        color_v[V].add(number)
        color_v[v].add(number)
        queue.append(v)
        number += 1

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])
### 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(R + 1):
    dp.append([[0] * (4) for _ in range(C + 1)])


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

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

from collections import defaultdict, deque

n, q = map(int, input().split())

tree = defaultdict(lambda: [])
for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

count = defaultdict(lambda: 0)
for _ in range(q):
    p, x = map(int, input().split())
    count[p] += x

ret = [0] * n
q = deque(maxlen=n)
q.append((1, 1))
while len(q) > 0:
    f, c = q.popleft()
    ret[c - 1] = count[c] + ret[f - 1]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)


### FIXED CODE ###

from collections import deque

d = ' '
n, q = map(int, input().split(d))

tree = [[] for _ in range(n)]

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

count = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split(d))
    p -= 1
    count[p] += x

ret = [0 for _ in range(n)]
q = deque(maxlen=n)
q.append((0, 0))
while len(q) > 0:
    f, c = q.popleft()
    ret[c] = count[c] + ret[f]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)
### BUGGY CODE ###

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = list(input())
N = len(S)

i = 1
cnt = 0
while i < N:
    if S[i-1] == 'B' and S[i] == 'W':
        S[i-1], S[i] = S[i], S[i-1]
        cnt += 1
        # 入れ替わったら、1マス後ろを再確認
        if i > 1: 
            i -= 2
    i += 1
print(cnt)


### FIXED CODE ###

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = list(input())
N = len(S)

ans = 0
w_sm = 0
for i in range(N):
    # Wを見つけたら、動かせるだけ左に動かす
    if S[i] == 'W':
        ans += i - w_sm
        # 今左に溜まっているWの数
        w_sm += 1
print(ans)