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

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))


### FIXED CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st.add(i)
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if j in st:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)
### BUGGY CODE ###

n = int(input())
mov = []
for i in range(5):
    mov.append(int(input()))
mov.reverse()

status = [0 for i in range(6)]
status[0] = n
status.reverse()

# print(mov)
# print(status)

count = 0
while True:
    count += 1
    for i in range(1,6):
        status[i-1] += min(status[i],mov[i-1])
        status[i] -= min(status[i],mov[i-1])
    if status[0]==n:
        print(count)
        exit()


### FIXED CODE ###

import math

n = int(input())
mov = []
for i in range(5):
    mov.append(int(input()))

print(math.ceil(n/min(mov))+4)
### BUGGY CODE ###

MOD=10**9+7
import sys
import math
N=int(input())
alist=list(map(int,input().split()))
alist.sort()

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
lcm=1
prod=1
for i in range(N):
  lcm=lcm*alist[i]*math.gcd(lcm,alist[i])
  prod*=alist[i]
  if lcm!=prod:    
    print("setwise coprime")
    sys.exit(0)
    
print("pairwise coprime")

### FIXED CODE ###

import sys
import math
N=int(input())
alist=list(map(int,input().split()))

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)

max_a=max(alist)  
dlist=[i for i in range(max_a+1)]
for i in range(2,int(max_a**0.5)+1):
  if dlist[i]<i:
    continue
  else:
    for j in range(i**2,max_a+1,i):
      dlist[j]=i  
#print(dlist)

fact_set=set()
for i in range(N):
  ai=alist[i]
  facts=set()
  while ai>1:
    facts.add(dlist[ai])
    ai//=dlist[ai]    
  #print(facts)
  
  for f in facts:
    if f in fact_set:
      print("setwise coprime")
      sys.exit(0)
    else:
      fact_set.add(f)
else:
  print("pairwise coprime")
### BUGGY CODE ###

N = int(input())
D = [int(_) for _ in input().split()]
M = int(input())
T = [int(_) for _ in input().split()]

D = sorted(D)
T = sorted(T)
Dstart = 0
flag = True

for i in T:
    for j in D[Dstart:]:
        Dstart += 1
        if i == j:
            break
        if Dstart == N:
            flag = False
    if not flag:
        break

print("YES" if flag else "NO")

### FIXED CODE ###

N = int(input())
D = [int(_) for _ in input().split()]
M = int(input())
T = [int(_) for _ in input().split()]

D = sorted(D)
T = sorted(T)
Tindex = 0
flag = False

for i in D:
    if i == T[Tindex]:
        Tindex += 1
        if Tindex == M:
            flag = True
            break

print("YES" if flag else "NO")
### BUGGY CODE ###

numBox, numnClild = [int(i) for i in input().split()]
numCandies = [int(i) for i in input().split()]

def find(left):
    acc = 0
    for i in range(left, numBox):
        acc += numCandies[i]
        if acc % numnClild == 0:
            return i + 1
    return -1

done_list = []
count = 0
for left in range(0, numBox):
    tmp_count = 0
    right = left
    while right != -1:
        right = find(right)
        if right != -1:
            if right in done_list:
                break
            else:
                done_list.append(right)
                tmp_count += 1
    count += int(tmp_count * (tmp_count + 1) / 2)
print(count)

### FIXED CODE ###

numBox, numClild = [int(i) for i in input().split()]
numCandies = [int(i) for i in input().split()]

subsequences = {}
acc = 0
for i in range(0, numBox):
    acc += numCandies[i]
    if (acc % numClild) in subsequences:
        subsequences[acc % numClild].append(i)
    else:
        subsequences[acc % numClild] = [i]

count = 0
for k, v in subsequences.items():
    count += int(len(v) * (len(v) - 1) / 2)
    if k == 0:
        count += len(v)
print(count)
### BUGGY CODE ###

from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで

def check(a,b,X):
  if a**5-b**5 == X:
    return 1
  else:
    return 0
  
def check2(a,b,X):
  if (a <= b+X) and (a > 0):
    return 1
  else:
    return 0

X = inp()
A = 0
tmp = 0
while 1:
  B = 1
  if A**5>X:
    need = 0
  else:
    need = 1
  reverse = 0
  if check(A,B,X):
    print(str(A)  + " " + str(B))
    break
  else:
    while 1:
      if B < A and A-X <= B:
        if check(A,B,X):
          print(str(A)  + " " + str(B))
          tmp = 1
          break
      else:
        break
      if reverse == 0 and need:
        B = (-1)*B
        reverse = 1
      elif reverse == 1:
        B = (-1)*B
        B = B + 1
        reverse = 0
  A += 1
  if tmp:
    break

### FIXED CODE ###

from math import ceil #切り上げ
import numpy as np
import sys
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで
 
def check(a,b,X):
  if a**5-b**5 == X:
    return 1
  else:
    return 0
  
X = inp()
for A in range(-118,120):
  for B in range(-119,119):
    if check(A,B,X):
      print(str(A) + " " + str(B))
      sys.exit()
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
P = list(map(int, input().split()))
uf = UnionFind(N)
for _ in range(M):
  x,y = map(int, input().split())
  uf.union(x-1,y-1)
from collections import defaultdict
d = defaultdict(lambda: [])
for i in range(N):
  d[uf.find(i)].append(i)
from bisect import bisect_left
def binary_search(A,p):
  A = sorted(A)
  if A[0]<=p and p<=A[-1]:
    if p == A[bisect_left(A,p)]:
      return True
  return False
ans = 0
for v in d.values():
  for a in v:
    if binary_search(v,P[a]-1):
      ans += 1
print(ans)


### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
P = list(map(int, input().split()))
uf = UnionFind(N)
for _ in range(M):
  x,y = map(int, input().split())
  uf.union(x-1,y-1)
from collections import defaultdict
d = defaultdict(lambda: [])
for i in range(N):
  d[uf.find(i)].append(i)
from bisect import bisect_left
def binary_search(A,p):
  if A[0]<=p and p<=A[-1]:
    if p == A[bisect_left(A,p)]:
      return True
  return False
ans = 0
for v in d.values():
  lis = sorted(v)
  for a in v:
    if binary_search(lis,P[a]-1):
      ans += 1
print(ans)
### BUGGY CODE ###

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()))

AB = [0]*X*Y
i = 0
for a in A:
    for b in B:
        AB[i] = a + b
        i += 1
AB.sort(reverse=True)

ans = [0]*min(K, len(AB))*Z
i, j = 0, 0
for i in range(min(K, len(AB))):
    for c in C:
        ans[j] = AB[i] + c
        j += 1
ans.sort(reverse=True)

for i in range(K):
    print(ans[i])

### FIXED CODE ###

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()))

AB = []
for i in range(X):
  for j in range(Y):
    AB.append(A[i] + B[j])
AB.sort(reverse=True)

ans = []
for i in range(min(K, len(AB))):
  for j in range(Z):
    ans.append(AB[i] + C[j])
ans.sort(reverse=True)

for i in range(K):
  print(ans[i])
### BUGGY CODE ###

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

l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * pow(10,index)
    temp %= 2019
    l[temp] += 1
    index += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

### FIXED CODE ###

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

l = [0] * 2019
temp = 0
e = 1
for i in range(N-1, -1, -1):
    temp += int(S[i]) * e
    temp %= 2019
    l[temp] += 1
    e *= 10
    e %= 2019

ans = l[0]

for i in range(0, 2019):
    ans += l[i] * (l[i]-1) // 2

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

a=int(input())
b=1
for i in range(1,a+1):
  b=b*i
  if b>1000000007:
    b=b-1000000007
if b<1000000000:
  print(b)
else:
  print(b%1000000007)


### FIXED CODE ###

a=int(input())
b=1
for i in range(1,a+1):
  b=b*i
  if b>1000000007:
    b=b%1000000007
if b<1000000000:
  print(b)
else:
  print(b%1000000007)
### BUGGY CODE ###

N,M=map(int,input().split())
A = list(map(int,input().split()))
for i in range(M):
  B,C=map(int,input().split())
  A = A + [C for j in range(B)] 
A.sort(reverse=True)
print(sum(A[0:N]))


### FIXED CODE ###

N,M=map(int,input().split())
A = list(map(int,input().split()))
bc = []

for i in range(N):
  bc.append( [1, A[i]])

for i in range(M):
  bc.append(list(map(int,input().split())))
bc = sorted( bc, key=lambda ii:ii[1], reverse=True)
p = []
tmp=0
for i in range(N):
  if bc[tmp][0] == 0:
    tmp +=1
  p.append( bc[tmp][1] )
  bc[tmp][0] -= 1
print( sum(p) )
### BUGGY CODE ###

def find_root(components, n):
    if components[n] == n:
        return n
    else:
        root =  find_root(components, components[n])
        components[n] = root
        return root

N, M = [int(s) for s in input().split(' ')]
bridges = []
for i in range(M):
    bridges.append([int(s)-1 for s in input().split(' ')])
components = [i for i in range(N)]
componentsLen = [1 for i in range(N)]
inconvenience = []
totalNpair = N * (N-1) / 2
for i in range(M-1, -1, -1):
    convenience = 0
    for c in range(N):
        convenience += componentsLen[c] * (componentsLen[c]-1) / 2
    inconvenience.append(int(totalNpair - convenience))
    a, b = bridges[i]
    a_root = find_root(components, a)
    b_root = find_root(components, b)
    if a_root != b_root:
        components[b_root] = a_root
        componentsLen[a_root] += componentsLen[b_root]
        componentsLen[b_root] = 1
for i in range(M-1, -1, -1):
    print(inconvenience[i])


### FIXED CODE ###

def find_root(components, n):
    if components[n] == n:
        return n
    elif components[components[n]] == components[n]:
        return components[n]
    else:
        components[n] = find_root(components, components[n])
        return components[n]

N, M = [int(s) for s in input().split(' ')]
bridges = []
for i in range(M):
    bridges.append([int(s)-1 for s in input().split(' ')])
components = [i for i in range(N)]
componentsLen = [1 for i in range(N)]
inconvenience = [int(N * (N-1) / 2)]
for i in range(M-1, -1, -1):
    a, b = bridges[i]
    a_root = find_root(components, a)
    b_root = find_root(components, b)
    if a_root != b_root:
        inconvenience.append(inconvenience[-1] - componentsLen[a_root] * componentsLen[b_root])
        if componentsLen[a_root] < componentsLen[b_root]:
            a_root, b_root = b_root, a_root
        componentsLen[a_root] += componentsLen[b_root]
        components[b_root] = a_root
    else:
        inconvenience.append(inconvenience[-1])
for i in range(M-1, -1, -1):
    print(inconvenience[i])
### BUGGY CODE ###

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

a.insert(0, 0)

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import collections

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

c = collections.Counter(a)

a.insert(0, 0)

for i in range(n):
    print(c[i+1])
### BUGGY CODE ###

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0 for s in range(a*n+1) ] for k in range(n+1) ] for j in range(n)]

for j in range(n):
    dp[j][0][0]=1
    if x[0]<= a*n:
        dp[j][1][x[0]] = 1

for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)

### FIXED CODE ###

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0 for s in range(a*n+1) ] for k in range(n+1) ] for j in range(n)]

for j in range(n):
    dp[j][0][0]=1
    if x[0]<= a*n:
        dp[j][1][x[0]] = 1

for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)
### BUGGY CODE ###

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

def search(n):
    if n == 0:
        return False
    for i in range(N-n):
        if i <= n:
            if S[i:i+n] in S[i+n:]:
                return True
        else:
            if S[i:i+n] in S[:i] + "|" + S[i+n:]:
                return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)


### FIXED CODE ###

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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 13 15:36:35 2019
ABC129D
@author: maezawa
"""

h, w = list(map(int, input().split()))
arr = [['*']*(w+2)]
for _ in range(h):
    arr.append(list('*' +input()+'*'))
arr.append(['*']*(w+2))

#result = arr[:]
#print(arr)

left = [[0]*(w+2) for _ in range(h+2)]
right = [[0]*(w+2) for _ in range(h+2)]
up = [[0]*(w+2) for _ in range(h+2)]
down = [[0]*(w+2) for _ in range(h+2)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if arr[i][j] == '#':
            left[i][j] = 0
        else:
            left[i][j] = left[i][j-1] + 1
for i in range(1, h+1):
    for j in reversed(range(1, w+1)):
        if arr[i][j] == '#':
            right[i][j] = 0
        else:
            right[i][j] = right[i][j+1] + 1
            
#print(left,sep='\n')
#print(right,sep='\n')

for j in range(1, w+1):
    for i in range(1, h+1):
        if arr[i][j] == '#':
            down[i][j] = 0
        else:
            down[i][j] = down[i-1][j] + 1
for j in range(1, w+1):
    for i in reversed(range(1, h+1)):
        if arr[i][j] == '#':
            up[i][j] = 0
        else:
            up[i][j] = up[i+1][j] + 1
            
maxlight = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if arr[i][j] == '#':
            continue
        n = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        #result[i][j] = n
        if n > maxlight:
            maxlight = n
            
print(maxlight)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 13 15:36:35 2019
ABC129D
@author: maezawa
"""

h, w = list(map(int, input().split()))
arr = [['*']*(w+2)]
for _ in range(h):
    arr.append(list('*' +input()+'*'))
arr.append(['*']*(w+2))

#result = arr[:]
#print(arr)

left = [[0]*(w+2) for _ in range(h+2)]
right = [[0]*(w+2) for _ in range(h+2)]
up = [[0]*(w+2) for _ in range(h+2)]
down = [[0]*(w+2) for _ in range(h+2)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if arr[i][j] == '#':
            left[i][j] = 0
        else:
            left[i][j] = left[i][j-1] + 1
for i in range(1, h+1):
    for j in reversed(range(1, w+1)):
        if arr[i][j] == '#':
            right[i][j] = 0
        else:
            right[i][j] = right[i][j+1] + 1
            
#print(left,sep='\n')
#print(right,sep='\n')

for j in range(1, w+1):
    for i in range(1, h+1):
        if arr[i][j] == '#':
            down[i][j] = 0
        else:
            down[i][j] = down[i-1][j] + 1
for j in range(1, w+1):
    for i in reversed(range(1, h+1)):
        if arr[i][j] == '#':
            up[i][j] = 0
        else:
            up[i][j] = up[i+1][j] + 1
            
maxlight = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if arr[i][j] == '#':
            continue
        n = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        #result[i][j] = n
        if n > maxlight:
            maxlight = n
            
print(maxlight)
### BUGGY CODE ###

Height, Width = map(int,input().split(" "))

lineBlocks = [(input()) for i in range(Height)]

twoDimMap = []
for Block in lineBlocks:
  twoDimMap.append(list(Block))

ansList = []
for i in range(Height):
  for j in range(Width):
    
    if '#' == twoDimMap[i][j]:
      continue

    else:
        k = i+1
        height_len = 0
        while( k < Height and twoDimMap[k][j] != "#"):
          height_len += 1
          k += 1
        
        k = i-1
        while( k >= 0 and twoDimMap[k][j] != "#"):
          height_len += 1
          k -= 1
    
        k = j+1
        width_len = 0
        while(k < Width and twoDimMap[i][k] != "#"):
          width_len += 1
          k += 1

        k = j-1
        while(k >= 0 and twoDimMap[i][k] != "#"):
          width_len += 1
          k -= 1

        light_range = height_len + width_len + 1
        ansList.append(light_range)
        
print(max(ansList))

### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
table = np.array([list(input())for _ in range(h)]) == '.'
 
d = np.zeros((h, w), dtype = int)
u = np.zeros((h, w), dtype = int)
r = np.zeros((h, w), dtype = int)
l = np.zeros((h, w), dtype = int)

for i in range(h):
    d[i] = (d[i-1]+1) * table[i]
    u[-i-1] = (u[-i]+1) * table[-i-1]

for i in range(w):
    r[:, i] = (r[:, i-1]+1) * table[:, i]
    l[:, -i-1] = (l[:, -i]+1) * table[:, -i-1]
print(np.max(d+u+r+l)-3)
### BUGGY CODE ###

N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
    cnt = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]: 
        if new == par:
            continue
        cnt[new] += cnt[cur]
        que.append([cur, new])
print(*cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)