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

from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(n):
        l = []
        if i > j:
            continue
        for k in range(n):
            if i != j:
                l.append(d[i][k] + d[k][j])
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)
### BUGGY CODE ###

import collections

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

for i in range(n):
    l = a[:i]+a[i+1:]
    pattern = 0
    pattern += sum([j*(j-1)//2 for j in collections.Counter(l).values()])
    print(pattern)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
d = collections.Counter(a)
s = sum([i*(i-1)//2 for i in d.values()])

for j in a:
    print(s-d[j]+1)
### BUGGY CODE ###

import fractions
K = int(input())
ans = 0


def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    else:
        return gcd(a, b % a)


for c in range(1, K+1):
    for b in range(1, K+1):
        for a in range(1, K+1):
            ans += fractions.gcd(fractions.gcd(a, b), c)
print(ans)


### FIXED CODE ###

K = int(input())
ans = 0


def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    else:
        return gcd(a, b % a)


for c in range(1, K+1):
    for b in range(1, K+1):
        for a in range(1, K+1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

#
# abc096 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
WEEWW"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """12
WEWEWEEEWWWE"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """8
WWWWWEEE"""
        output = """3"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    S = list(input())

    ans = float("inf")
    for i in range(N):
        if i == 0:
            ans = min(ans, S[1:].count("E"))
        elif i == N-1:
            ans = min(ans, S[0:N-1].count("W"))
        else:
            ans = min(ans, S[0:i].count("W") + S[i+1:].count("E"))

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc096 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
WEEWW"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """12
WEWEWEEEWWWE"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """8
WWWWWEEE"""
        output = """3"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    S = list(input())

#    ans = float("inf")
#    for i in range(N):
#        if i == 0:
#            ans = min(ans, S[1:].count("E"))
#        elif i == N-1:
#            ans = min(ans, S[0:N-1].count("W"))
#        else:
#            ans = min(ans, S[0:i].count("W") + S[i+1:].count("E"))
#    print(ans)

    W = [0] * N
    E = [0] * N
    L = 0
    R = 0

    for i in range(N):
        if S[i] == "W":
            L += 1
        if S[N-1-i] == "E":
            R += 1
        W[i] = L
        E[N-1-i] = R

    ans = float("inf")
    for i in range(N):
        ans = min(ans, E[i]+W[i]-1)
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()
### BUGGY CODE ###

H, N = map(int, input().split())
a, b = [0]*N, [0]*N
for i in range(N):
    a[i], b[i] = map(int, input().split())
dp = [[float('inf')] * (H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(H+1):
        if j - a[i] <= 0:
            dp[i+1][j] = min(dp[i][j],b[i])
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
print(dp[N][H])

### FIXED CODE ###

H, N = map(int, input().split())
a, b = [0]*N, [0]*N
for i in range(N):
    a[i], b[i] = map(int, input().split())
dp = [[float('inf')] * (H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(H+1):
        if j - a[i] <= 0:
            dp[i+1][j] = min(dp[i][j],b[i])
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
print(dp[N][H])
### BUGGY CODE ###

n=5*10**4
p=[True]*n
p[0],p[1]=False,False
for i in xrange(2,int(n**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,n,i):
            p[j]=False
while True:
    n=input()
    if n==0:break
    c=0
    for i in xrange(n/2+1):
        if p[i] and p[n-i]:c+=1
    print c

### FIXED CODE ###

import itertools
N=50000+1
p=[True]*N
p[0],p[1]=False,False
for i in xrange(2,int(N**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,N,i):
            p[j]=False
plist=[i for i in xrange(N) if p[i]]
c=[0]*N*2
for i,j in itertools.combinations(plist,2):
    c[i+j]+=1
for i in xrange(N):
    if p[i]:c[i+i]+=1
while True:
    n=input()
    if n==0:break
    print c[n]
### BUGGY CODE ###

import numpy as np


def main():
    H, W = map(int, input().split())
    A = np.array(
        [list(map(lambda x: int(x) % 2,
                  input().split())) for _ in range(H)])
    AB = np.zeros([2, H, W], dtype=np.int32)
    AB[0, :, :] = A
    AB[1, :, :] = np.reshape(np.arange(H * W), [H, W])
    for i in range(1, H, 2):
        AB[0, i, :] = AB[0, i, :][::-1]
        AB[1, i, :] = AB[1, i, :][::-1]

    C = np.zeros([2, H * W], dtype=np.int32)
    C[0] = AB[0].flatten()
    C[1] = AB[1].flatten()

    aa = []
    for i in range(len(C[0]) - 1):
        if C[0, i] % 2 == 0:
            continue
        else:
            C[0, i] -= 1
            C[0, i + 1] += 1
            aa.append((C[1, i], C[1, i + 1]))

    print(len(aa))
    for a, b in aa:
        w0, h0 = divmod(a, W)
        w1, h1 = divmod(b, W)
        print(w0 + 1, h0 + 1, w1 + 1, h1 + 1)


main()


### FIXED CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    H, W = map(int, readline().split())
    A = np.array([
        list(map(lambda x: int(x) % 2,
                 readline().split())) for _ in range(H)
    ])

    aa = []
    for h in range(H):
        for w in range(W - 1):
            if A[h, w] == 1:
                A[h, w + 1] += 1
                aa.append([h + 1, w + 1, h + 1, w + 2])

    for h in range(H - 1):
        w = W - 1
        if A[h, w] % 2 != 0:
            A[h + 1, w] += 1
            aa.append([h + 1, w + 1, h + 2, w + 1])

    print(len(aa))

    for a in aa:
        print(*a)


main()
### BUGGY CODE ###

a,b=[int(j) for j in input().split()]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
la=set(make_divisors(a))
lb=set(make_divisors(b))
l=list(la&lb)
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

ans=0
ll=set([1])
l.sort()
for i in l:
    if i==1:
        continue
    if set(make_divisors(i))&ll=={1}:
        ll.add(i)
print(len(ll))


### FIXED CODE ###

a,b=[int(j) for j in input().split()]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
la=set(make_divisors(a))
lb=set(make_divisors(b))
l=list(la&lb)
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

ans=0
ll=set([1])
l.sort()
for i in l:
    if i==1:
        continue
    if set(make_divisors(i))&ll=={1}:
        ll.add(i)
print(len(ll))
### BUGGY CODE ###

import copy
n = int(input())
x = [int(y) for y in input().split()]
z = copy.deepcopy(x)

for i in range(n):
  x.pop(i)
  x.sort()
  print(x[int((n - 1) / 2)])
  del x[:]
  x.extend(z)

### FIXED CODE ###

import copy
import statistics
n = int(input())
x = [int(y) for y in input().split()]
z = copy.deepcopy(x)
z.sort()
t = (z[int(n / 2) - 1] + z[int(n / 2)]) / 2

for i in range(n):
  if x[i] < t:
    print(z[int(n / 2)])
  else:
    print(z[int(n / 2) - 1])
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    S = input()

    res = float('inf')
    for i in range(N):
        temp = 0
        for j in range(N):
            if i > j and S[j] == 'W':
                temp += 1
            elif i < j and S[j] == 'E':
                temp += 1
        if res > temp:
            res = temp

    print(res)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    S = input()

    numE = S.count('E')
    numW = S.count('W')

    #index iの要素はiより左側にいてかつ西を向いている
    #人の人数を表す
    sumW = [0]
    for i in range(N):
        if S[i] == 'W':
            sumW.append(sumW[i] + 1)
        else:
            sumW.append(sumW[i])

    sumE = []
    for i in range(N):
        sumE.append(numE-i+sumW[i])
        if S[i] == 'E':
            sumE[i] -= 1
    att = []
    for i in range(N):
        att.append(sumW[i] + sumE[i])

    print(min(att))
### BUGGY CODE ###

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

A = []
for i in P:
    A.append(1/2*(i+1))

ans = 0
for i in range(len(A)):
    ans = max(ans,sum(A[i:i+K]))

print(ans)

### FIXED CODE ###

from itertools import accumulate

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

A = []
for i in P:
    A.append(1/2*(i+1))
    #A.append(1/2*i*(i+1)/i)

ans = 0
'''
for i in range(len(A)):
    ans = max(ans,sum(A[i:i+K]))
'''
    
accum = [0] + list(accumulate(A))
for i in range(len(accum)):
    ans = max(ans,accum[i] - accum[i-K])
print(ans)
### BUGGY CODE ###

import collections
from scipy.special import comb

n = int(input())
aa = list(map(int, input().split()))
xx = [0]*n
for i in range(n):
  a = 0
  if i == 0:
    bb = aa[1:]
  elif i == n-1:
    bb = aa[:-1]
  else:
    bb = aa[:i] + aa[i+1:]
  cc = collections.Counter(bb)
  d = [c[1] for c in cc.items()]
  for j in range(len(d)):
    a += comb(d[j], 2, exact=True)
  xx[i] = a
  
for i in range(n):
  print(xx[i])


### FIXED CODE ###

import collections

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

c = collections.Counter(a)
for i in c:
  cnt += c[i]*(c[i]-1)//2



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

import sys
input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    Ass = [tuple(map(int, input().split())) for _ in range(H)]
    Bss = [tuple(map(int, input().split())) for _ in range(H)]

    dp = [[set() for j in range(W)] for i in range(H)]
    A, B = Ass[0][0], Bss[0][0]
    dp[0][0] = set([abs(A-B)])

    for i in range(H):
        for j in range(W):
            if i < H-1:
                A, B = Ass[i+1][j], Bss[i+1][j]
                for diff in dp[i][j]:
                    dp[i+1][j].add(abs(diff+A-B))
                    dp[i+1][j].add(abs(diff+B-A))
            if j < W-1:
                A, B = Ass[i][j+1], Bss[i][j+1]
                for diff in dp[i][j]:
                    dp[i][j+1].add(abs(diff+A-B))
                    dp[i][j+1].add(abs(diff+B-A))

#    for dpi in dp:
#        print(dpi)
    ans = min(dp[-1][-1])
    print(ans)


solve()


### FIXED CODE ###

maxV = 80*(80+80)

H, W = map(int, input().split())
Ass = [tuple(map(int, input().split())) for _ in range(H)]
Bss = [tuple(map(int, input().split())) for _ in range(H)]

dp = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        A, B = Ass[i][j], Bss[i][j]
        if A > B:
            A, B = B, A
        if i == 0 and j == 0:
            dp[i][j] = 1<<(maxV+B-A) | 1<<(maxV-B+A)
        if i > 0:
            dp[i][j] |= dp[i-1][j]<<(B-A) | dp[i-1][j]>>(B-A)
        if j > 0:
            dp[i][j] |= dp[i][j-1]<<(B-A) | dp[i][j-1]>>(B-A)

bitset = dp[-1][-1]
mask = 1<<(2*maxV)
ans = maxV
for i in range(-maxV, maxV+1):
    if bitset & mask:
        ans = min(ans, abs(i))
    mask >>= 1

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

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# s = "AACACTTTTAC"
# print(s.count("AC"))#3

lr=[]
s2 = ""
n, q = map(int, input().split())
s = input()
for i in range(q):
        l,r = map(int, input().split())
        lr.append([l,r])

for i in range(q):
        s2 = s[lr[i][0] - 1:lr[i][1]]
        # print(s2)
        print(s2.count("AC"))


### FIXED CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
lr = []
for i in range(q):
        l,r = map(int, input().split())
        lr.append([l,r])

n = len(s)
L = 0
R = 1
cntAC = [0] * n

for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        cntAC[i] += 1

# 累積和
cSum = np.cumsum(cntAC)


for _lr in lr:
    if _lr[L] == 1:
        print(cSum[_lr[R]-2])
    else:
        print(cSum[_lr[R]-2] - cSum[_lr[L]-2])
        

"""
ACACTACG
"""
### BUGGY CODE ###

import sys
input = sys.stdin.readline
R, C, K = map(int, input().split())

L_INF = int(1e17)
dp = [[[-L_INF] * 4 for _ in range(C+1)] for _ in range(R+1)]
cell = [[0] * (C+1) for _ in range(R+1)]

for i in range(K):
    x, y, c = map(int, input().split())
    cell[x-1][y-1] = c

dp[0][1][0] = dp[1][0][0] = 0

for i in range(1, R + 1):
    for j in range(1, C + 1):
        for k in range(4):
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
            if k == 1:
                dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

print(dp[R][C][3])


### FIXED CODE ###

import sys
import numpy as np
from numba import jit, void, i8
input = sys.stdin.readline

def main():
    R, C, K = map(int, input().split())

    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    cell = np.full((R+1, C+1), 0, dtype=np.int64)

    for i in range(K):
        x, y, c = map(int, input().split())
        cell[x-1][y-1] = c

    f(dp, cell, R, C)

    print(dp[R][C][3])

@jit(void(i8[:,:,:],i8[:,:],i8,i8))
def f(dp, cell, R, C):
    dp[0][1][0] = dp[1][0][0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

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

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)] 
          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    #dic = {}
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        #cnt = 0
        while q:
            now = q.popleft()
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    #cnt +=1
                    q.append(f)
        #dic[nxt] = cnt
        try:
            nxt = fl.index(-1)
        except:
            nxt = 0
    dic = collections.Counter(fl)
    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])-1
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

import sys
input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)
def Nodify(n):
    for i in graph[n]:
        if Tree[i]==-1:
            Tree[i]=n
            Nodify(i)
def solve(n):
    for i in graph[n]:
        if i==Tree[n]:
            pass
        else:
            ans[i]=ans[n]+counter[i]
            solve(i)
n,q=map(int,input().split())
graph=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
Tree=[-1]*n
Nodify(0)
Tree[0]=-1
counter=[0 for _ in range(n)]
for _ in range(q):
    p,x=map(int,input().split())
    counter[p-1]+=x
ans=[-1]*n
ans[0]=counter[0]
solve(0)
for i in ans:
    print(i,end=" ")

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)
n,q=map(int,input().split())
graph=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
counter=[0]*n
for _ in range(q):
  p,x=map(int,input().split())
  counter[p-1]+=x
score=[0]*(n+1)
stack=[(0,-1)]
while stack!=[]:
  node,prev=stack.pop()
  score[node]=score[prev]+counter[node]
  for i in graph[node]:
    if i!=prev:
      stack.append((i,node))
print(*score[:-1])
### BUGGY CODE ###

#D問題
import math
H,W,A,B = map(int,input().split())
mod = 10**9 + 7

M = H+W-1
fact = [1 for i in range(M)]
for i in range(M):
    if i == 0:
        pass
    else:
        fact[i] = (fact[i-1]*i)%mod
        
refact = [1 for i in range(M)]
m = mod-2
b = bin(m)
b = b.lstrip("0b")
b = b[::-1]
m2 = len(b)
for i in range(M):    
    flog = [0 for j in range(m2)]
    for j in range(m2):
        if j == 0:
            flog[0] = fact[i]
        else:
            flog[j] = (flog[j-1]**2)%mod
    #print(flog)
    for j in range(m2):
        if b[j] == "1":
            refact[i]*=flog[j]
            refact[i]%=mod
            
row = B
wide = W-B
ans = 0
for i in range(wide):
    row = B+i
    C1 = (fact[H-A+row-1]*refact[H-A-1]*refact[row])%mod
    C2 = (fact[W+A-row-2]*refact[W-row-1]*refact[A-1])%mod
    #print(C1,C2)
    ans+=C1*C2
    ans%=mod

#print(fact)
#print(refact)

print(ans)

### FIXED CODE ###

#D問題
import math
H,W,A,B = map(int,input().split())
mod = 10**9 + 7

M = H+W-1
fact = [1 for i in range(M)]
for i in range(M):
    if i == 0:
        pass
    else:
        fact[i] = (fact[i-1]*i)%mod
        
refact = [1 for i in range(M)]
m = mod-2
b = bin(m)
b = b.lstrip("0b")
b = b[::-1]
m2 = len(b)
for i in range(M):    
    flog = [0 for j in range(m2)]
    for j in range(m2):
        if j == 0:
            flog[0] = fact[i]
        else:
            flog[j] = (flog[j-1]**2)%mod
    #print(flog)
    for j in range(m2):
        if b[j] == "1":
            refact[i]*=flog[j]
            refact[i]%=mod
            
row = B
wide = W-B
ans = 0
for i in range(wide):
    row = B+i
    C1 = (fact[H-A+row-1]*refact[H-A-1]*refact[row])%mod
    C2 = (fact[W+A-row-2]*refact[W-row-1]*refact[A-1])%mod
    #print(C1,C2)
    ans+=C1*C2
    ans%=mod

#print(fact)
#print(refact)

print(ans)