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

import numpy as np
h, w = map(int, input().split())

s = np.zeros((h, w))
for i in range(h):
    for j, c in enumerate(list(str(input()))):
        if c == ".":
            s[i][j] = 1

board_w = np.zeros((h, w))
board_h = np.zeros((w, h))

# 横、縦の順に走査
for i in range(h):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == 1:
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == w - 1:
            for k in range(cnt_continue):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0

s = s.transpose()

for i in range(w):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == 1:
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == h - 1:
            for k in range(cnt_continue):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0

board_h = board_h.transpose()
ans = 0

for i in range(h):
    for j in range(w):
        v = int(board_w[i][j] + board_h[i][j])
        ans = max(ans, v)

print(ans-1)

### FIXED CODE ###

h, w = map(int, input().split())

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

board_w = [[0 for _ in range(w)] for _ in range(h)]
board_h = [[0 for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_w[i][j] = cnt_continue

    for j in reversed(range(w-1)):
        if board_w[i][j] == 0:
            continue
        board_w[i][j] = max(board_w[i][j], board_w[i][j+1])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_h[j][i] = cnt_continue

    for j in reversed(range(h-1)):
        if board_h[j][i] == 0:
            continue
        board_h[j][i] = max(board_h[j][i], board_h[j+1][i])


ans = 0

for i in range(h):
    for j in range(w):
        v = board_w[i][j] + board_h[i][j] - 1
        ans = max(ans, v)

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

n, m = map(int, input().split())
a = [0]*m
for i in range(m):
  a[i] = int(input())

r = [0]*(n+1)
r[0] = 1
if 1 in a:
  r[1] = 0
else:
  r[1] = 1
for i in range(2, n+1):
  if i in a:
    r[i] = 0
  else:
    r[i] = r[i-1] + r[i-2]

print(r[n]%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
a = [0]*m
for i in range(m):
  a[i] = int(input())

up = [0]*(m+1)
if m == 0:
  up[0] = n
else:
  up[0] = a[0]-1
  up[m] = n - a[m-1]-1
  for i in range(m-1):
    up[i+1] = a[i+1]-a[i]-2

ans = 1
if -1 in up:
  ans = 0
else:
  f = [0]*(max(up)+1)
  f[0] = 1
  if max(up) > 0:
    f[1] = 1
    for i in range(2, max(up)+1):
      f[i] = f[i-1] + f[i-2]
  for i in range(m+1):
    ans *= f[up[i]]

print(ans % 1000000007)
### BUGGY CODE ###

S = input()
T = input()

len_S = len(S)
S_Converted = list(S) 
for i in range (len(S)):
    tmp_S = S_Converted[i]
    tmp_T = T[i]
    if tmp_S == tmp_T:
        continue
    list_indexS = [j for j, tmp_SC in enumerate(S_Converted) if tmp_SC == tmp_S]
    list_indexT = [j for j, tmp_SC in enumerate(S_Converted) if tmp_SC == tmp_T]
    for li in list_indexS:
        S_Converted[li] = tmp_T
    #S_Converted[list_indexS] = tmp_T
    for li in list_indexT:
        if li == i:
            continue
        else:
            S_Converted[li] = tmp_S
    #print(''.join(S_Converted))
S_Converted = ''.join(S_Converted)

if S_Converted == T:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys

S = input()
T = input()

len_S = len(S)
S_Converted = S
for i in range (len(S)):
    tmp_S = S_Converted[i]
    tmp_T = T[i]
    if tmp_S == tmp_T:
        continue
    S_Converted = list(S_Converted) 
    list_indexT = [j for j, tmp_SC in enumerate(S_Converted) if tmp_SC == tmp_T]
    if (not list_indexT == []) and (list_indexT[0] < i):
        print('No')
        sys.exit()
    S_Converted = ''.join(S_Converted)
    S_Converted = S_Converted.replace(tmp_S, tmp_T)
    S_Converted = list(S_Converted) 
    for li in list_indexT:
        if li == i:
            continue
        else:
            S_Converted[li] = tmp_S
    #print(''.join(S_Converted))
    
S_Converted = ''.join(S_Converted)

if S_Converted == T:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

T_MAX = 10**5
n, nc = list(map(int, input().split()))
stc = [list(map(int, input().split())) for _ in range(n)]

nrecs = [0]*(2*T_MAX+1)
for c in range(1, nc+1):
    rec = [0]*(2*T_MAX+1)
    for i in range(n):
        if stc[i][2] == c:
            rec[stc[i][0]*2-1] += 1
            rec[stc[i][1]*2] -= 1
    for i in range(1, 2*T_MAX+1):
        rec[i] += rec[i-1]
    for i in range(2*T_MAX+1):
        if rec[i] > 0:
            nrecs[i] += 1
    
print(max(nrecs))


### FIXED CODE ###

T_MAX = 10**5
n, nc = list(map(int, input().split()))
stc = [list(map(int, input().split())) for _ in range(n)]

recs = [[0]*(T_MAX+1) for c in range(nc+1)]
for s, t, c in stc:
    recs[c][s-1:t] = [1]*(t-s+1)

ans = max(map(sum, zip(*recs)))
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ba = []
m1 = m + 2
check = set()
for _ in range(n):
    a,b = map(int,input().split())
    ba.append([b,a])
ba.sort(reverse=True)
cnt = 0
for BA in ba:
    a1 = BA[1]#a
    b1 = BA[0]#b
    if a1 >= m1:
        continue
    mb = m1
    m1 = a1
    for i in range(m - a1 + 1):
        if a1 + i not in check:
            check.add(a1 + i)
            cnt += b1
            m1 = mb
            break
print(cnt)

### FIXED CODE ###

from heapq import *
# from itertools import permutations
# from math import pi
# from operator import itemgetter
# from operator import mul
# from operator import xor
# from os import linesep


# def isprime(n: int) -> bool:
#     if n <= 1:
#         return False
#     if n in (2, 3, 5):
#         return True
#     if n % 2 == 0:
#         return False
#     if n % 3 == 0:
#         return False
#     lst = int(n**0.5)
#     f = 5
#     while f <= lst:
#         if n % f == 0:
#             return False
#         if n % (f + 2) == 0:
#             return False
#         f += 6
#     return True


# def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
#     return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


# def strbool(boolval: int) -> str:
#     return ['No', 'Yes'][boolval]


def solve() -> None:
    # read here
    n, m, *t = map(int, open(0).read().split())

    # solve here
    d = [[] for i in range(m+1)]
    for i in range(n):
        a, b = t[2*i], t[2*i+1]
        if a > m:
            continue
        d[a].append(b)

    ans = 0
    tasks = []
    for t in range(m + 1):
        # from (m days after) to today
        for tasksize in d[t]:
            heappush(tasks, -tasksize)
        if tasks:
            # do task
            ans -= heappop(tasks)

    # print here
    print(ans)


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

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

d = dict()
for a_i in a:
	if a_i not in d:
		d[a_i] = 0
	d[a_i] += 1
d = sum([[d_i[0] for i in range(d_i[1]//2)] for d_i in d.items()], [])

if len(d) < 2:
	print(0)
else:
	max_1 = max(d)
	d.remove(max_1)
	max_2 = max(d)
	print(max_1 * max_2)

### FIXED CODE ###

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

a.sort()
maxs = []
for i in range(2):
	max_1 = a.pop()
	while True:
		max_2 = a.pop()
		if max_1 == max_2:
			maxs.append(max_1)	
			break
		max_1 = max_2
		if len(a) == 0:
			print(0)
			exit()
print(maxs[0]*maxs[1])
### BUGGY CODE ###

n=int(input())
A=list(map(int, input().split(" ")))
count=0
num1=0
num2=0
a=[[]]
b=[[]]
count=0


for i in range(n):
    xors=0
    sums=0
    for k in range(n-i):
        if xors^A[k+i] == sums+A[k+i]:
            #print(i,k+i)
            count+=1
        else:
            break
        xors=xors^A[k+i]
        sums=sums+A[k+i]
print(count)


### FIXED CODE ###

n=int(input())
A=list(map(int, input().split(" ")))
count=0

xors=0
sums=0
r=0
for l in range(n):
    while (r != n and xors^A[r] == sums+A[r]):
        sums += A[r]
        xors ^= A[r]
        r += 1
    count+=r-l
    xors^=A[l]
    sums-=A[l]
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    _ = int(readline())
    As = list(map(int, readline().split()))
    sorted_As = sorted(As)
    order = []
    for A in sorted_As:
        order.append(As.index(A))
    order = [str(o+1) for o in order]
    print(' '.join(order))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    _ = int(readline())
    As = list(map(int, readline().split()))
    order = np.argsort(As)
    order = [str(o + 1) for o in order]
    print(' '.join(order))


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

N= int(input())

# queryを投げて空の時の処理をする関数
def query1(i):
  print(i)
  tmp = input()
  if tmp[0] == 'V':
    exit()
  return r

# 最初に始点を探索
z = query1(0)
  
# 矛盾していないか判定する関数, Falseなら矛盾
def judge1(m):
  s = query1(m)
  if m % 2 == 0: # 偶数なら0番目と同じなら矛盾しない
    return z==s
  else:
    return z!=s
  
# 二分探索する
l = 0
r = N # N-1にするとN-1が探索されずにwhileを抜けてしまう
while r - l > 1:
  m = (l + r) // 2
  if judge1(m):
    # l~mまでが矛盾しない
    l = m
  else:
    r = m

### FIXED CODE ###

N= int(input())

# queryを投げて空の時の処理をする関数
def query1(i):
  print(i)
  tmp = input()
  if tmp[0] == 'V':
    exit()
  return tmp

# 最初に始点を探索
z = query1(0)
  
# 矛盾していないか判定する関数, Falseなら矛盾
def judge1(m):
  s = query1(m)
  if m % 2 == 0: # 偶数なら0番目と同じなら矛盾しない
    return z==s
  else:
    return z!=s
  
# 二分探索する
l = 0
r = N # N-1にするとN-1が探索されずにwhileを抜けてしまう
while r - l > 1:
  m = (l + r) // 2
  if judge1(m):
    # l~mまでが矛盾しない
    l = m
  else:
    r = m
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    s = str(input())
    S.append(s)

T = list(set(S))
t = 1
U = []
for i in range(len(T)):
    x = S.count(T[i])
    if t < x:
        t = x
        U = [T[i]]
    elif t == x:
        U.append(T[i])

U_ = list(sorted(U))
for i in range(len(U_)):
    print(U_[i])

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
    s = str(input())
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

S = sorted(dic.values())
t = S[-1]

X = []
for key in dic:
    if dic[key] == t:
        X.append(key)
x = sorted(X)

for i in range(len(X)):
    print(x[i])
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
#import numpy as np
#import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s = input()
q = int(input())
ql = [input().split() for i in range(q)]

isrev=False
for i in range(q):
  if ql[i][0] == '1':
    isrev = not isrev
    continue
  if (ql[i][1] == '2') == isrev:
    s=ql[i][2]+s
  else:
    s=s+ql[i][2]
if isrev:
  s = s[::-1]

print(s)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
#import numpy as np
#import scipy
from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s = input()
q = int(input())
ql = [input().split() for i in range(q)]

ans = deque(s)
isrev=False
for i in range(q):
  if ql[i][0] == '1':
    isrev = not isrev
    continue
  if (ql[i][1] == '2') == isrev:
    ans.appendleft(ql[i][2])
  else:
    ans.append(ql[i][2])

if isrev:
  ans.reverse()

s = ''.join(ans)

print(s)
### BUGGY CODE ###

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

Answer = 1
for i in range(N):
    Answer *= A[i]

if Answer > 1000000000000000000:
    print(-1)
else:
    print(Answer)


### FIXED CODE ###


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

B = set(A)
Answer = 1
if 0 in B:
    print(0)
    exit()
for i in range(N):
    Answer *= A[i]
    if Answer > 1000000000000000000:
        print(-1)
        exit()
print(Answer)
### BUGGY CODE ###

n = int(input())
words_list = list()
cnt = []
ans = []
for i in range(n) :
    words_list.append(input())
candidates = list(set(words_list))
for word in candidates :
    cnt.append(words_list.count(word))
mx = max(cnt)
for i in range(len(cnt)) :
    if cnt[i] == mx :
        ans.append(candidates[i])
ans = sorted(ans)
for i in range(len(ans)) :
    print(ans[i])


### FIXED CODE ###

n = int(input())
d = {}
for _ in range(n) :
    s = input()
    if s in d :
        d[s] += 1
    else :
        d[s] = 1

mx = max(d.values())
for s in sorted(k for k in d if d[k] == mx) :
    print(s)
### BUGGY CODE ###

S = input()
N = len(S)

while True:
    fn = len(S)
    S = S.replace('01', '').replace('10','')
    if fn == len(S):
        break

print(N - len(S))

### FIXED CODE ###

S = input()
N = len(S)
A = 0

for i in range(N):
    if S[i] == '1':
        A = A + 1

print(min(N - A, A)*2)
### BUGGY CODE ###

def main():
    x = int(input())
    c = x%5
    while x%c!=0:
        c+=5
    ans = (x-c**5)/c/5
    def f(x):
        return c**3*x + 2*c**2*x**2+2*c*x**3+x**4-ans
    if f(0)>0:
        b=-1
        while f(b)!=0:
            b-=1
    elif f(0)==0:
        b = 0
    else:
        b=1
        while f(b)!=0:
            b+=1
    print(int(b+c),int(b))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    x = int(input())
    for a in range(1,120):
        for b in range(-120,120):
            if a**5-b**5==x:
                print(a,b)
                return
        

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

N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    ans = 0
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
      
  

        

### FIXED CODE ###

from collections import deque
N = int(input())
X = str(input())
X = list(X)
#motokosu = X.count("1")
motokosu = 0
only = float("inf")
for i in range(N):
  if X[i] == "1":
    motokosu += 1
    only = i
if motokosu != 1:
  only = float("inf")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu

pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu >= 1:
      mmotosuji = (mmotosuji+M[i])%mkosu
#print(P,M,pkosu,mkosu,pmotosuji,mmotosuji)

for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
#print(motokosu)
### BUGGY CODE ###

import math

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

def waribiki(s,maisu):
    return math.floor(s/(2**maisu))

for _ in range(m):
    a.append(waribiki(max(a),1))
    a.remove(max(a))

print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
 
for i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))
### BUGGY CODE ###

import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
# divisor = 10 ** 9 + 7
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mod)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = mod13_list[(s * mod)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp % (10 ** 9 + 7)
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = mod13_list[(mod * 10)]
print(dp_[5] % (10 ** 9 + 7))

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

from sys import stdin


def mod(val):
    res = val % (10 ** 9 + 7)
    if (res < 0):
        res += (10 ** 9 + 7)
    return res


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = list(map(int, _in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    A_arr_mod = [0] * len(A_arr)
    for i, a in enumerate(A_arr):
        A_arr_mod[i] = mod(a)

    ans = 0
    for i in range(N-1):
        ans += A_arr_mod[i] * sum(A_arr_mod[i+1:])
    ans = mod(ans)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def mod(val):
    res = val % (10 ** 9 + 7)
    if (res < 0):
        res += (10 ** 9 + 7)
    return res


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = list(map(int, _in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    A_arr_mod = [0] * len(A_arr)
    for i, a in enumerate(A_arr):
        A_arr_mod[i] = mod(a)

    ans = 0
    cache = sum(A_arr_mod)
    for i in range(N-1):
        cache -= A_arr_mod[i]
        ans += A_arr_mod[i] * cache
        ans = mod(ans)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


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

from collections import deque
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]

chil = [[] for _ in range(N+1)]
count = [0]*(N+1)

for ab in AB:
    chil[ab[0]].append(ab[1])
    chil[ab[1]].append(ab[0])

def cleanse(fromN, toN):
#    print('fromN:', fromN)
#    print('toN:', toN)
    chil[toN].remove(fromN)
    if len(chil[toN])==0:  # leaf
        return
    for node in chil[toN]:
        cleanse(toN, node)

#print(chil)

for node in chil[1]:
    cleanse(1, node)

def addition(fromN, toN, value):
#    print('fromN:', fromN)
#    print('toN:', toN)
    count[toN] += value
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        addition(toN, node, value)

#print(chil)

for px in PX:
    count[px[0]] += px[1]
    for node in chil[px[0]]:
        addition(px[0], node, px[1])

print(*count[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

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

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

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)