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

# =============================================================================
#　ABC138D Ki
# =============================================================================
import sys
sys.setrecursionlimit(10**8)

N,Q=map(int,input().split())
cnt=[0]*(N+1)
ans=[0]*(N+1)
Graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for _ in range(Q):
    v,x=map(int,input().split())
    cnt[v]+=x

def dfs(Graph,v,x,p):
    global ans
    ans[v]=x
    for nv in Graph[v]:
        if nv==p:
            continue
        nx=x+cnt[nv]
        dfs(Graph,nv,nx,v)

dfs(Graph,1,cnt[1],-1)
ans=[str(ans[i]) for i in range(1,N+1)]
print(" ".join(ans))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


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

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

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])
### BUGGY CODE ###

import sys
si = sys.stdin.readline


def main():
    [x, k, d] = [int(e) for e in si().split()]
    if x == 0:
        if k % 2 == 0:
            print(0)
        else:
            print(abs(d))
    elif x < 0:
        while x < 0 and k:
            x += d
            k -= 1
        if k > 0:
            if k % 2:
                print(abs(x-d))
            else:
                print(x)
        else:
            print(abs(x))
    else:
        while x > 0 and k:
            x -= d
            k -= 1
        if k > 0:
            if k % 2:
                print(x+d)
            else:
                print(abs(x))
        else:
            print(abs(x))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
si = sys.stdin.readline


def main():
    [x, k, d] = [int(e) for e in si().split()]
    if x == 0:
        if k % 2 == 0:
            print(0)
        else:
            print(abs(d))
    elif x < 0:
        mul = (0-x)//d
        if k <= mul:
            x += d*k
            print(abs(x))
            return
        else:
            x += d*mul
            k -= mul
        while x < 0 and k:
            x += d
            k -= 1
        if k > 0:
            if k % 2:
                print(abs(x-d))
            else:
                print(x)
        else:
            print(abs(x))
    else:
        mul = (x-0)//d
        if k <= mul:
            x -= d*k
            print(x)
            return
        else:
            x -= d*mul
            k -= mul
        while x > 0 and k:
            x -= d
            k -= 1
        if k > 0:
            if k % 2:
                print(x+d)
            else:
                print(abs(x))
        else:
            print(abs(x))


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

def Replacing():

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

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

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        value_A = [value_B[1] if j == value_B[0] else j for j in value_A]

        print(sum(value_A))

if __name__ == '__main__':
    Replacing()


### FIXED CODE ###

from collections import Counter

def Replacing():

    Num = int(input())

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

    Sum = sum(value_A)
    Counter_value = Counter(value_A)

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        Sum += (value_B[1] - value_B[0])*Counter_value[value_B[0]]
        Counter_value[value_B[1]] += Counter_value[value_B[0]]
        Counter_value[value_B[0]] = 0

        print(Sum)

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

N = int(input())
S = []
C = []
M = 1
for i in range(N):
  s = input()
  if s in S:
    n = S.index(s)
    C[n] += 1
    if C[n] > M:
      M = C[n]
  else:
    S.append(s)
    C.append(1)
l = len(C)
A = [S[j] for j in range(l) if C[j] == M]
A.sort()
[print(k) for k in A]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

N, M = map(int, input().split())
al = []
for i in range(M):
  al.append(tuple(input().split()))
al_a = [i[0] for i in al if i[1] == 'AC']
al_a = list(set(al_a))
r1 = len(al_a)
r2 = 0
for j in al:
  if j[0] in al_a:
    if j[1] == 'AC':
      al_a.remove(j[0])
    else:
      r2 += 1
    
print(r1 ,r2)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    ac = [0] * n
    wanum = [0] * n
    for _ in range(m):
        p, s = input().split()
        p = int(p) - 1
        if ac[p]:
            continue
        else:
            if s == 'AC':
                ac[p] = 1
                wanum[p] *= -1
            else:
                wanum[p] -= 1
    wanum2 = [i for i in wanum if i > 0]
    print(sum(ac), sum(wanum2))

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

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def isp(x):
    if x == 1:
        return False
    elif x == 2:
        return True
    elif not x & 1:
        return False
    maxv = floor(sqrt(x))+1
    for i in range(3, maxv+1, 2):
        if x % i == 0: return False
    return True

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    for i in range(l, r+1):
        if isp(i) and isp((i+1)//2):ans += 1
    print(ans)


### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 1
    for i in range(2, l):
        if not isp[i]: continue
        for j in range(i*2, n, i): isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1
#print(cnt[:10])
acc = list(accumulate(cnt))
for _ in range(q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import Counter


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

    for i in range(N):
        print(Counter(A)[i + 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter(A)

    for i in range(N):
        print(count[i + 1])


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

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    if N < 5*(10**4) :
        parameter = 0.997
    else :
        parameter = 0.9999
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import collections

h, w, m = map(int, input().split())
x = []
y = []
bomb = []
for i in range(m):
  tmp_x, tmp_y = map(int, input().split())
  x.append(tmp_x)
  y.append(tmp_y)
  bomb.append([tmp_x, tmp_y])

c_x = collections.Counter(x)
c_y = collections.Counter(y)
_max_x = c_x.most_common()[0][1]
_max_y = c_y.most_common()[0][1]

count = 0
for i in bomb:
  if c_x[i[0]] == _max_x and c_y[i[1]] == _max_y:
    count += 1

if count == len([kv[0] for kv in c_x.items() if kv[1] == max(c_x.values())]) * len([kv[0] for kv in c_y.items() if kv[1] == max(c_y.values())]):
  print(_max_x + _max_y - 1)
else:
  print(_max_x + _max_y)

### FIXED CODE ###

h,w,n=map(int,input().split())
H=[0]*h
W=[0]*w
L=[(0,0)]*n
for i in range(n):
    a,b=map(int,input().split())
    L[i]=(a,b)
    H[a-1]+=1
    W[b-1]+=1
h_max=max(H)
w_max=max(W)
ans=h_max+w_max
cnt=0
for l in L:
    if H[l[0]-1]==h_max and W[l[1]-1]==w_max:
        cnt+=1
if H.count(h_max)*W.count(w_max)==cnt:
    ans-=1
print(ans)
### BUGGY CODE ###

h, w, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

from collections import defaultdict
d = defaultdict(int)

dp = [0] * 10
dp[0] = (h - 2) * (w - 2)
for i in range(n):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            nx, ny = a + dx, b + dy # center
            if nx >= 1 and nx <= h - 2 and ny >= 1 and ny <= w - 2:
                # print(nx, ny)
                tmp = 0
                for dx2 in [-1, 0, 1]:
                    for dy2 in [-1, 0, 1]:
                        if d[str(nx + dx2) + ' ' + str(ny + dy2)] == 1:
                            tmp += 1

                dp[tmp] -= 1
                dp[tmp + 1] += 1
    d[str(a) + ' ' + str(b)] = 1
    # print(dp)

for d in dp:
    print(d)


### FIXED CODE ###

h, w, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

d = dict()
for i in range(len(ab)):
    a = ab[i][0] - 1
    b = ab[i][0] - 1
    d[a] = set()

dp = [0] * 10
dp[0] = (h - 2) * (w - 2)
for i in range(n):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            nx, ny = a + dx, b + dy # center
            if nx >= 1 and nx <= h - 2 and ny >= 1 and ny <= w - 2:
                # print(nx, ny)
                tmp = 0
                for dx2 in [-1, 0, 1]:
                    for dy2 in [-1, 0, 1]:
                        if nx + dx2 in d and ny + dy2 in d[nx + dx2]:
                            tmp += 1

                dp[tmp] -= 1
                dp[tmp + 1] += 1

    d[a].add(b)

for x in dp:
    print(x)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + spc_list[q_idx][0] * spc_list[q_idx][1] + spc_list[q_idx][2] < G:
                score += spc_list[q_idx][0] * spc_list[q_idx][1] + spc_list[q_idx][2]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G or q_num > min_q:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                q_num += min(math.ceil((G-score) / spc_list[q_idx][0]), spc_list[q_idx][1])
                score = G
                """
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
"""
            if score >= G:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


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

n,k = map(int,input().split())
li = list(map(int,input().split()))
ans = 0
li_2 = []
for i in range(n-k+1):
  num = sum(li[i:i+k])
  li_2.append(num)
print(max(li_2)*0.5 + 0.5*k)

### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())
li = list(map(int,input().split()))
ruisekiwa = list(np.cumsum(li))
ruisekiwa.insert(0,0)
ans = []
for i in range(n-k+1):
  num = ruisekiwa[i+k]-ruisekiwa[i]
  ans.append(num)
print(0.5*max(ans) + 0.5*k)
### BUGGY CODE ###


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


def dfs2(conj, p=0, t=0, past_p=None, visit=set(), second_visit=set()):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        # p から q への引継ぎ処理
        X[q] += X[p]
        dfs2(conj, q, t+1, p, visit, second_visit)
    second_visit.add(p)
    return X

######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, M:辺

conj = [set() for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1                                    # デクリメントが不要な場合は消す
    v -= 1
    conj[u].add(v)
    conj[v].add(u)                            # 無効グラフの場合は消す

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

print(*dfs2(conj, p=0))

### FIXED CODE ###

import sys

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

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

branch = [[] for _ in range(N)] # [[]]*N だと参照渡しになってしまう
X = [0,]*N
root = [None]*N
t = 0

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

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


def search(p):
    global t
    root[p-1] = t
    t += 1
    for q in branch[p-1]:
        if root[q-1] != None:
            continue
        X[q - 1] += X[p - 1]
        search(q)
    t -= 1



search(1)
print(*X)
### BUGGY CODE ###

N = int(input())
INF = float('inf')
A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
A = sorted(A, key=lambda x: x[1], reverse = True)

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

for s in range(1, N+1):
  for l in range(s+1):
    r = s - l
    dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
ans = 0
for m in range(N):
  if(dp[m][N-m] > ans):
    ans = dp[m][N-m]
    
print(ans)



### FIXED CODE ###

def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

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

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()
### BUGGY CODE ###

from collections import deque

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

    A=list(map(lambda x:int(x)-1,input().split()))

    loop=[]
    slack=[]

    flag=0
    t=0
    start=0
    while flag==0:
        slack.append(t)
        t=A[t]
        if (t in slack):
            start=slack.index(t)
            flag=1

    slack_num=start
    loop_num=len(slack)-slack_num

    # print(slack)
    # print(start)
    # print(slack_num)
    # print(loop_num)
    #
    loop=slack[start:]
    # print(loop)
    if (K-slack_num)<0:
        res=slack[K]+1
    else:
        tele_num=((K-slack_num)%loop_num)
        town=loop[tele_num]
        res=town+1

    print(res)

if __name__=="__main__":
    main()



### FIXED CODE ###

from collections import deque

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

    A=list(map(lambda x:int(x)-1,input().split()))
    FootPrintA=A[:]

    loop=[]

    slack_que=deque([])
    flag=0
    t=0
    start=0
    while flag==0:
        slack_que.append(t)
        t_ = FootPrintA[t]
        FootPrintA[t]=-1
        if t_==-1:
            start=slack_que.index(t)
            flag=1
            slack_que.pop()
        t = A[t]

    slack=list(slack_que)
    slack_num=start
    loop_num=len(slack)-slack_num

    # print(slack)
    # print(start)
    # print(slack_num)
    # print(loop_num)
    #
    loop=slack[start:]
    # print(loop)
    if (K-slack_num)<0:
        res=slack[K]+1
    else:
        tele_num=((K-slack_num)%loop_num)
        town=loop[tele_num]
        res=town+1

    print(res)

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

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
# 1 2 3 4
ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        for c in range(b + 1, N):
            if nums[a] + nums[b] > nums[c]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        ind = bisect.bisect_left(nums, nums[a] + nums[b])
        ans += ind - 1 - b
print(ans)
### BUGGY CODE ###

import numpy as np
from math import log2
from collections import defaultdict
from operator import itemgetter
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7


BIT_len = 2 ** 18 # = 262144 > 200000
BIT_MOD = np.zeros(BIT_len+1, np.int64)

def BIT_add(index, elem):
    global BIT_len, BIT_MOD
    index += 1
    while index <= BIT_len:
        BIT_MOD[index] += elem
        BIT_MOD[index] %= MOD
        index += index & -index

def BIT_sum(index):
    global BIT_len, BIT_MOD
    index += 1
    s = 0
    while index != 0:
        s += BIT_MOD[index]
        s %= MOD
        index -= index & -index
    return s


d = defaultdict(list)

N = int(input())
for i in range(N):
    C = int(input())
    d[C].append(i)

pairs = []
for c, indices in d.items():
    for i in range(len(indices) - 1):
        if indices[i+1] - indices[i] > 1:
            pairs.append((indices[i], indices[i+1]))

pairs.sort(key = itemgetter(1))   


BIT_add(0, 1)
for start, end in pairs:
    BIT_add(end, BIT_sum(start))

print(BIT_sum(N))


### FIXED CODE ###

import numpy as np
from collections import defaultdict
from operator import itemgetter
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7


d = defaultdict(list)

N = int(input())
for i in range(N):
    C = int(input())
    d[C].append(i)

pairs = []
for c, indices in d.items():
    for i in range(len(indices) - 1):
        if indices[i+1] - indices[i] > 1:
            pairs.append((indices[i], indices[i+1]))

pairs.sort(key = itemgetter(1))   


dp = np.zeros(N, np.int64)
dp[0] = 1
index = 0
for i in range(1, N):
    dp[i] = dp[i-1]
    while index < len(pairs) and pairs[index][1] == i:
        dp[i] += dp[pairs[index][0]] 
        index += 1
    dp[i] %= MOD

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

import itertools
l = []
n,m,q=map(int, input().split())

tmp = 0
max = 0
tmpmax=0
c = []

for i in range(q):
    c.append([int(j) for j in input().split()])

for i in range(q):
    tmpmax = tmpmax + c[i][3]

for i in range(1,m+1):
    l.append(str(i))
a = list(itertools.combinations_with_replacement(l, n))

for k in range(len(a)): 
    for i in range(q):
        if int(a[k][c[i][1]-1]) - int(a[k][c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
        if tmpmax == max:
            print(max)
            exit()
    tmp = 0

print(max)


### FIXED CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
  A, B, C, D = map(int, input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[b[i]-1]) - int(retsu[a[i]-1]) == c[i]:
            tmp = tmp + d[i]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)
### BUGGY CODE ###

from decimal import Decimal
n=int(input())
p=list(map(Decimal,input().split()))

dp=[[0]*(n+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(n):
        dp[j][i+1]+=dp[j][i]*(1-p[i])
        dp[j+1][i+1]+=dp[j][i]*p[i]

ans=0
for j in range((n+1)//2,n+1):
    ans+=dp[j][-1]
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(float,input().split()))

dp=[[0]*(n+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(n):
        dp[j][i+1]+=dp[j][i]*(1-p[i])
        dp[j+1][i+1]+=dp[j][i]*p[i]

ans=0
for j in range((n+1)//2,n+1):
    ans+=dp[j][-1]
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
E = [[] for _ in range(N)]
C = [0] * N
C[0] = 0
for _ in range(N - 1):
  a, b = map(int, input().split())
  E[a - 1].append(b - 1)
  E[b - 1].append(a - 1)
for _ in range(Q):
  p, x = map(int, input().split())
  C[p - 1] += x
D = [-1] * N
D[0] = 0
Q = [0]
while Q:
  q = Q.pop(0)
  for adj in E[q]:
    if D[adj] >= 0:
      continue
    D[adj] = D[q] + 1
    C[adj] += C[q]
    Q.append(adj)
print(' '.join([str(c) for c in C]))

### FIXED CODE ###

N, Q = map(int, input().split())
E = [[] for _ in range(N)]
C = [0] * N
C[0] = 0
for _ in range(N - 1):
  a, b = map(int, input().split())
  E[a - 1].append(b - 1)
  E[b - 1].append(a - 1)
for _ in range(Q):
  p, x = map(int, input().split())
  C[p - 1] += x
D = [-1] * N
D[0] = 0
Q = [0] * N
enq = 0
for pos in range(N):
  q = Q[pos]
  for adj in E[q]:
    if D[adj] >= 0:
      continue
    D[adj] = D[q] + 1
    C[adj] += C[q]
    enq += 1
    Q[enq] = adj
print(' '.join([str(c) for c in C]))