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

from collections import deque
 
ADS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
 
H, W = map(int, input().split(" "))
A = [list(input()) for _ in range(H)]

q = deque()
for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            q.append((x, y))

count = 0
while q:
    r = list(q)
    q = deque()
    for q_i in r:
        this_pos = this_x, this_y = q_i
        
        for ad_x, ad_y in ADS:
            pos = x, y = this_x+ad_x, this_y+ad_y
            if not ((0 <= x < W) and (0 <= y < H)):
                continue
            if A[y][x] == "#":
                continue
            A[y][x] = "#"
            q.append(pos)
    count += 1
    # print(A, count, q)

print(count-1)

### FIXED CODE ###

from collections import deque
from itertools import chain

INF = 10**18

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

q = deque([])
dist = [[INF for _ in range(W)]for _ in range(H)]
for y, A_line in enumerate(A):
    for x, a in enumerate(A_line):
        if a == "#":
            dist[y][x] = 0
            q.append((x, y))

while q:
    t_pos = tx, ty = q.popleft()
    dist_t = dist[ty][tx]

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        elif A[y][x] == "#":
            continue
        elif dist[y][x] <= dist_t + 1:
            continue
        dist[y][x] = dist_t + 1
        q.append(pos)
# print(dist)

r = max(chain(*dist))
print(r)
### BUGGY CODE ###

h,w = map(int,input().split())
S = [input() for i in range(h)]

A = [[0 for i in range(w)] for j in range(h)]

a = -1
b = -1
for i in range(h):
    a = -1
    for j in range(w):
        if S[i][j] == "#":
            if a != -1:
                for k in range(a,j):
                    A[i][k] += j-a
                a = -1
        else:
            if a == -1:
                a = j
                #print(j)
    if a != -1:
        for k in range(a,j+1):
            A[i][k] += j+1-a

for i in range(w):
    a = -1
    for j in range(h):
        if S[j][i] == "#":
            if a != -1:
                for k in range(a,j):
                    A[k][i] += j-a
                a = -1
        else:
            if a == -1:
                a = j
    if a != -1:
        for k in range(a,j+1):
            A[k][i] += j+1-a
#print(A)

ans = 0
for i in range(h):
    ans = max(ans, max(A[i]))

print(ans-1)

### FIXED CODE ###

h,w = map(int,input().split())
S = [input() for i in range(h)]

A = [[0 for i in range(w)] for j in range(h)]

a = -1
b = -1
for i in range(h):
    a = -1
    for j in range(w):
        if S[i][j] == "#":
            if a != -1:
                for k in range(a,j):
                    A[i][k] += j-a
                a = -1
        else:
            if a == -1:
                a = j
                #print(j)
    if a != -1:
        for k in range(a,j+1):
            A[i][k] += j+1-a

for i in range(w):
    a = -1
    for j in range(h):
        if S[j][i] == "#":
            if a != -1:
                for k in range(a,j):
                    A[k][i] += j-a
                a = -1
        else:
            if a == -1:
                a = j
    if a != -1:
        for k in range(a,j+1):
            A[k][i] += j+1-a
#print(A)

ans = 0
for i in range(h):
    ans = max(ans, max(A[i]))

print(ans-1)
### BUGGY CODE ###

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

a_tax = int(a / 0.08)
b_tax = int(b / 0.1)
n  = min([a_tax, b_tax])

while True:
    if a == int(n * 0.08) and b == int(n * 0.1):
        break
    
    n += 1

print(n)

### FIXED CODE ###

a, b = map(int, input().split())
for i in range(2000):
    if int(i * 0.08) == a and int(i * 0.1) == b:
        print(i)
        break
else:
    print(-1)
### BUGGY CODE ###

S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])

### FIXED CODE ###

S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
for i in range(N):
  A=A*L[i]
if 10**18<A:
  print(-1)
else:
  print(A)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
if 0 in L:
  print(0)
  exit()
for i in range(N):
  A=A*L[i]
  if 10**18<A:
    print(-1)
    exit()
print(A)
### BUGGY CODE ###

import copy
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[2],x[0],x[1]))

W = []
for v in V:
	W.append([v[0]-v[2],v[1]-v[2]-1])
w = W[:]
for m in M:
	for n in range(N):
		w[n].append(m)
		w[n].sort()
		if w[n][1] == m:
			print(V[n][2])
			w[n].remove(m)
			break
		w[n].remove(m)
	else:
		print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

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

ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += a_s[i] * a_s[j]

print(int(ans % (1e9 + 7)))


### FIXED CODE ###

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

sum_a = 0
mul_a = 0
mod = 1000000007

for a in a_s:
    sum_a += a
    mul_a += a*a
    sum_a %= mod
    mul_a %= mod

ans = sum_a * sum_a
ans %= mod
ans -= mul_a
ans %= mod

n = mod-2
inv = 1
base = 2

while n:
    if n & 1:
        inv = inv*base % mod
    base = base*base % mod
    n >>= 1

ans *= inv
ans %= mod

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

import copy
N=int(input())
L=[int(x) for x in input().split()]
L0=copy.copy(L)
L.sort()
Ans=[]

for i in range(N):
	for j in range(N):
		if L[i]==L0[j]:
			Ans.append(j+1)

print(' '.join(map(str, Ans)))

### FIXED CODE ###

import copy
N=int(input())
L=[int(x) for x in input().split()]
Ans=[0]*N

for i in range(N):
	Ans[L[i]-1]=i+1

print(' '.join(map(str, Ans)))
### BUGGY CODE ###

import collections
S=input()
l=len(S)
t=0
p=0
m=[]
ss=[0]
for i in range(l):
    m.append(int(S[i])*(10**(l-1-i))%2019)
    ss.append((ss[i]+m[i])%2019)

k=collections.Counter(ss)

for i in k.values():
    if i>1:
        t+=(i-1)
print(t)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

def primesUpTo(n):
    primes = [2]
    if n < 2:
        return []

    for i in range(3, n + 1, 2):
        isPrime = True
        for prime in primes[1:]:
            if prime > n ** (1 / 2):
                break
            if i % prime == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(i)

    return primes

n = int(input())
l = [int(input()) for _ in range(n)]
primes = primesUpTo(max(l))

print(len([x for x in l if x in primes]))


### FIXED CODE ###

def isPrime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            return False

    return True

n = int(input())
cnt = 0
for _ in range(n):
    i = int(input())
    cnt += isPrime(i)

print(cnt)
### BUGGY CODE ###

N = int(input())
path = []
ans = 0
ap = path.append
for i in range(N):
    A = int(input())
    ap([])
    for j in range(A):
        x, y = map(int,input().split())
        x -= 1
        path[-1].append((x, y))
for i in range(1<<N):
    i |= (1<<N)
    judge = True
    for j in range(N):
        if (1<<j) & i:
            for k in range(len(path[j])):
                if path[j][k][1] != int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
    if judge:
        if ans < bin(i).count("1") - 1:
            ans = bin(i).count("1") - 1
print(ans)

### FIXED CODE ###

N = int(input())
path = []
ans = 0
for i in range(N):
    A = int(input())
    path.append([])
    for j in range(A):
        x, y = map(int,input().split())
        x -= 1
        path[-1].append((x, y))
for i in range(1<<N):
    i |= (1<<N)
    judge = True
    for j in range(N):
        if not judge:
            break
        if (1<<j) & i:
            for k in range(len(path[j])):
                if path[j][k][1] != int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
                    break
    if judge:
        if ans < bin(i).count("1") - 1:
            ans = bin(i).count("1") - 1
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
n=200
ans = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=(gcd(i,j,k))
print(ans)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
n=int(input())
ans = 0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if i==j==k:
              ans+=gcd(i+1,j+1,k+1)
            elif i<j<k:
              ans+=6*(gcd(i+1,j+1,k+1))  
            else:
              ans+=3*(gcd(i+1,j+1,k+1))
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
c=0
for i in range(q):
    s1=input()
    if s1[0]=='1':
        c+=1
    else:
        if s1[2]=='1':
            if c%2==0:
                s=s1[4]+s
            else:
                s+=s1[4]
        else:
            if c%2==0:
                s+=s1[4]
            else:
                s=s1[4]+s
if c%2==0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s=list(input())
q=int(input())
c=0
left=[]
right=[]
for i in range(q):
    s1=input()
    if s1[0]=='1':
        c+=1
    else:
        if s1[2] == '1':
            if c % 2 == 0:
                left.append(s1[4])
            else:
                right.append(s1[4])
        else:
            if c % 2 == 0:
                right.append(s1[4])
            else:
                left.append(s1[4])
left=left[::-1]
left.extend(s)
left.extend(right)
if c%2==0:
    print(''.join(left))
else:
    left=left[::-1]
    print(''.join(left))
### BUGGY CODE ###

from collections import deque
def main():
    n,x,y = map(int,input().split())
    cnt = [0]*(n)
    res = []
    for i in range(n):
        d = [float('inf')]*n
        que = deque([(i, 0)])
        while que:
            idx, c = que.popleft()
            if d[idx]!=float('inf'):
                d[idx] = min(d[idx], c)
                continue
            else:
                d[idx] = min(d[idx], c)
                if idx!=0:
                    que.append((idx-1, c+1))
                if idx!=n-1:
                    que.append((idx+1, c+1))
                if idx==x-1:
                    que.append((y-1, c+1))
                if idx==y-1:
                    que.append((x-1, c+1))
        res.append(d)
    
    for r in res:
        for i in range(n-1):
            cnt[i] += r.count(i)
    for c in cnt[1:]:
        print(c//2)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
n,x,y = map(int,input().split())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
cnt = [0]*n
for i in range(n):
    for j in range(i+1, n):
        cnt[g[i][j]] += 1
for c in cnt[1:]:
    print(c)
### BUGGY CODE ###

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

cnt = 0
for i in range(n):
    ok_flag = True
    for j in range(i+1):
        if p[i] > p[j]:
            ok_flag=False
    if ok_flag:
        cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
min_1_i = p[0]
for i in range(n):
    min_1_i = min(min_1_i,p[i])
    if p[i] <= min_1_i:
        cnt += 1

print(cnt)
### BUGGY CODE ###

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

def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    past=[[] for i in range(n)] 
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
            if(d[j]>d[v]+cost[v][j]):
                d[j]=d[v]+cost[v][j]
                past[j].append(v)
            else:
                d[j]=d[j]
                # past[j].append(j)



    return d,used,past

cost = [[float("inf") for i in range(n)] for i in range(n)] 

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

ans,used,past= dijkstra(0,n,m,cost)
if(False in used):print("No")
else:
    print("Yes")
    for i in past[1:]:
        print(i[0]+1)

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)
### BUGGY CODE ###

n = int(input())
ar = [[] for i in range(n)]
for i in range(n-1):
    ipt = list(map(int,input().split()))
    ar[ipt[0]-1].append([ipt[1]-1,ipt[2]])
    ar[ipt[1]-1].append([ipt[0]-1,ipt[2]])

ans = [[] for i in range(n)]
u = 0
ans[u] = 0
queue = [u] #キュー
check = [False]*n #訪問済み
check[u] = True

while True:
    if len(queue) == 0:
        break
    u = queue.pop(0)
    for v in ar[u]:
        if not check[v[0]]:
            check[v[0]] = True
            ans[v[0]] = ans[u] + v[1]
            queue.append(v[0])

for i in range(len(ans)):
    print(ans[i]%2)

### FIXED CODE ###

n = int(input())
ar = [[] for i in range(n)]
for i in range(n-1):
    ipt = list(map(int,input().split()))
    ar[ipt[0]-1].append((ipt[1]-1,ipt[2]))
    ar[ipt[1]-1].append((ipt[0]-1,ipt[2]))

ans = [-1 for i in range(n)]
u = 0
ans[u] = 0
queue = [u] #キュー
l = 1
while True:
    if l == 0:
        break
    u = queue.pop(0)
    l -= 1
    for v in ar[u]:
        if ans[v[0]] < 0:
            ans[v[0]] = ans[u] + v[1]
            queue.append(v[0])
            l+=1

for i in range(n):
    print(ans[i]%2)
### BUGGY CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = input()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    N = 14
    K = 2
    S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N:
    cnt = 1
    if S[i] == "0":
      i += 1
      while i < N:
        if S[i] == "0":
          cnt += 1
          i += 1
        else:
          break
    else:
      i += 1
      while i < N:
        if S[i] == "1":
          cnt += 1
          i += 1
        else:
          break
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  i = 0
  lenSC = len(SC) - 1
  ans = 0
  while i <= lenSC:
    cnt = 0
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    for j in range(i,k + 1):
      cnt += SC[j]
    if ans < cnt:
      ans = cnt
    i += 2

  print(ans)

main()

### FIXED CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()
### BUGGY CODE ###

import sys
import itertools

N = int(input())
L = list(map(int, sys.stdin.readline().split()))

c_list = list(itertools.combinations(L, 3))
count = 0

for v in c_list:
    if v[0] < v[1] + v[2] and v[1] < v[0] + v[2] and v[2] < v[0] + v[1]:
        count += 1
        
print(count)

### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
L.sort()

count = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        c = bisect.bisect_left(L, L[i]+L[j])
        if c > j:
            count += c - j - 1
        else:
            pass
        
print(count)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50

def dfs(current, node_vals, seen, to):
    for next, val in enumerate(to[current]):
        if val and not seen[next]:
            node_vals[next] += node_vals[current]
            seen[next] = 1
            dfs(next, node_vals, seen, to)


def run():
    N, Q = map(int, sysread().split())
    to = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N-1):
        a,b = map(int,sysread().split())
        to[a][b] = 1
        to[b][a] = 1

    node_vals = [0] * (N+1)

    for i in range(Q):
        p, x = map(int, sysread().split())
        node_vals[p] += x

    seen = [0] * (N+1)
    seen[1] = 1
    dfs(1, node_vals, seen, to)

    node_vals = [str(v) for v in node_vals]
    print(' '.join(node_vals[1:]))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50

def dfs(current, node_vals, seen, to):
    for next in to[current]:
        if not seen[next]:
            node_vals[next] += node_vals[current]
            seen[next] = 1
            dfs(next, node_vals, seen, to)


def run():
    N, Q = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(N-1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    node_vals = [0] * (N+1)

    for i in range(Q):
        p, x = map(int, sysread().split())
        node_vals[p] += x

    seen = [0] * (N+1)
    seen[1] = 1
    dfs(1, node_vals, seen, to)

    node_vals = [str(v) for v in node_vals]
    print(' '.join(node_vals[1:]))

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

n,m=list(map(int, input().split()))
h=list(map(int, input().split()))
p=[]
remain = set(range(1, n+1))
for i in range(m):
    p.append(list(map(int, input().split())))
temp = []
for a,b in p:
    temp.append([b,a])
p = p + temp
for a,b in p:
    if h[a-1]<=h[b-1]:
        remain = remain - set([a])
print(len(remain))

### FIXED CODE ###

n,m=list(map(int, input().split()))
h=list(map(int, input().split()))
p=[]
remain = set(range(1, n+1))
for i in range(m):
    p.append(list(map(int, input().split())))
temp = []
for a,b in p:
    temp.append([b,a])
p = p + temp
delset = set()
for a,b in p:
    if h[a-1]<=h[b-1]:
        #remain = remain - set([a])
        delset.add(a)
remain = remain - delset
print(len(remain))
### BUGGY CODE ###

n, a, b = [int(i) for i in input().split()]
c = 0
s = []
while c < n:
  s += [1 for _ in range(a)]
  s += [0 for _ in range(b)]
  c = len(s)
print(sum(s[:n]))

### FIXED CODE ###


n, a, b = [int(i) for i in input().split()]
sy = n // (a+b)
am = n % (a+b)
print(sy*a + min(am, a))