Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]

n,m=map(int,input().split())
#xyz = [[]for i in range(m)]
g = [[]for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

seen = [0 for i in range(n)]

def dfs(i):
    for nec in g[i]:
        if seen[nec]!=0:continue
        seen[nec]=1
        dfs(nec)

cnt = 0
for i in range(n):
    if seen[i] == 0:
        seen[i] = 1
        dfs(i)
        cnt+=1

print(cnt)


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
#xyz = [[]for i in range(m)]
g = [[]for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

seen = [0 for i in range(n)]

def dfs(i):
    for nec in g[i]:
        if seen[nec]!=0:continue
        seen[nec]=1
        dfs(nec)

cnt = 0
for i in range(n):
    if seen[i] == 0:
        seen[i] = 1
        dfs(i)
        cnt+=1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)


Fixed submission:
H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0

for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)


Fixed submission:
H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)
Buggy python submission (verdict: Runtime Error):
N = int(input())
nums = list(map(int, input().split()))
nums.sort()

# 解説の通りに実装
num_max = nums[-1]
exist_counts = [0] * (num_max + 1)
for num in nums:
  # すでにcountされてる場合、重複であることだけ残して抜ける
  if exist_counts[num]:
    exist_counts[num] = 2
    continue
  # はじめてのcountであれば、自分自身とその倍数にチェックをつける
  idx = num
  while idx < num_max:
    exist_counts[idx] += 1
    idx += num

# 各numについて、count=1ならば条件を満たしたということ
count = 0
for num in nums:
  if exist_counts[num] == 1:
    count += 1
print(count)

Fixed submission:
lst = list(map(int, input().split()))
print(lst.index(0) + 1)
Buggy python submission (verdict: Runtime Error):
import sys
import copy
import numpy as np
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline

if __name__ == '__main__':
#  cnt=0
  def dfs(C,t,hw,i):
    global k
    global h
    global w
    #print(t,k)
    #print(C)
    if t==k:
      return 1
    elif t<k:
      return 0
    if hw=='w' and i==w:
      return 0
    C1=copy.copy(C)
    C2=copy.copy(C)
    if hw=='h':
      #print(i,C1,np.zeros((1,w)))
      C1[i]=np.zeros((1,w))
      #print(C1)
      #exit(0)
      hw='w' if i==h-1 else 'h'
      i=0 if hw=='w' else i+1
      return dfs(C1,np.sum(C1),hw,i)+dfs(C2,np.sum(C2),hw,i)
    else:
      #print(C1)
      #C1[:][i]=np.zeros((h,1))
      for j in range(h):
        #tmp=C1[j]
        C1[j][i]=0
      #print(C1)
      #exit(0)
      i+=1
      return dfs(C1,np.sum(C1),hw,i)+dfs(C2,np.sum(C2),hw,i)

#  C=[[0 for _ in range(6)] for _ in range(6)]
  h,w,k=map(int,input().strip("\n").split())
  C=np.zeros((h,w))
  #print(C)
  for i in range(h):
    s=[1 if c=='#' else 0 for c in input().strip("\n")]
    #print(s)
    C[i]=np.array(s)
  #sprint(np.sum(C))
  print(dfs(copy.copy(C),np.sum(C),'h',0))


Fixed submission:
import sys
input = sys.stdin.readline

if __name__ == '__main__':
  h,w,k=map(int,input().strip("\n").split())
  s=[]
  for i in range(h):
    s.append(list(input().strip("\n")))
  ans=0
  #print(s)
  # 2 -> 100 rangeだから11まで
  for iS in range(1<<h):
    # 3->1000=2^3=8
    for js in range(1<<w):
      #print(iS,js)
      cnt=0
      for i in range(h):
        for j in range(w):
          # 赤で塗る場合
          # ex)iS=01,i=0->i+1桁目が1か
          if iS>>i&1: continue
          if js>>j&1: continue
          if s[i][j]=='#': cnt+=1
      if cnt==k: ans+=1

  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  ans=0
  d=[0]*(n+1)
  for i in range(1,n+1):
    for j in range(i,n+1,i):
      d[j]+=1
  for i in range(1,n+1):
    ans+=i*d[i]
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  ans=0
  d=[0]*(n+1)
  for i in range(1,n+1):
    for j in range(i,n+1,i):
      d[j]+=1
  for i in range(1,n+1):
    ans+=i*d[i]
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))
ans=1
LIMIT=10**18
for i in range(n):
  ans*=A[i]
if ans>LIMIT:
  ans=-1
print(ans)


Fixed submission:
n=int(input())
A=list(map(int,input().split()))
ans=1
LIMIT=10**18

if 0 in A:
  print(0)
else:
  for i in range(n):
    ans*=A[i]
    if ans>LIMIT:
      ans=-1
      break
  print(ans)
Buggy python submission (verdict: Runtime Error):
n=input().split()
a=int(n[0])
b=int(eval(n[1]+'*100'))
print(b)
if b<1:
  print(int(a*b))
else:
  #print(int(b*100)*a)
  print(int(str(b*a)[:-2]))


Fixed submission:
from decimal import Decimal
a,b=map(Decimal,input().split())
print(int(a*b))

Buggy python submission (verdict: Runtime Error):
n=input().split()
a=int(n[0])
b=float(n[1])
if b<1:
  print(int(a*b))
else:
  print(int(str(int(b*100)*a)[:-2]))



Fixed submission:
from decimal import Decimal
a,b=map(Decimal,input().split())
print(int(a*b))
Buggy python submission (verdict: Runtime Error):
import numpy as np

def dfs(n,a,s):
  if n==0:
    return -1 if (a >= X).all()==False else s
  #print(a+A[n-1])
  x=dfs(n-1,a+A[n-1],s+C[n-1])
  y=dfs(n-1,a,s)
  return y if x==-1 else x if y==-1 else min(x,y)

N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  c,*tmp=map(int,input().split())
  A.append(np.array(tmp))
  C.append(c)
#print(A)
print(dfs(N,np.array([0]*M),0))



Fixed submission:
import numpy as np

def dfs(n,a,s):
  if n==0:
    return -1 if (a >= X).all()==False else s
  #print(a+A[n-1])
  x=dfs(n-1,a+A[n-1],s+C[n-1])
  y=dfs(n-1,a,s)
  return y if x==-1 else x if y==-1 else min(x,y)

N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  c,*tmp=map(int,input().split())
  A.append(np.array(tmp))
  C.append(c)
#print(A)
print(dfs(N,np.array([0]*M),0))
Buggy python submission (verdict: Runtime Error):
x=int(input())

for i in range(-118,120):
  for j in range(-119,119):
    if i**5-j**5==x:
      print(i,j)
      exit(1)


Fixed submission:
x=int(input())
# an = n^5 - (n - 1)^5
# a -> 120~-119 -> -118~119
# b -> 119~-120 -> -119~118
for i in range(-118,120):
  for j in range(-119,119):
    if i**5-j**5==x:
      print(i,j)
      exit()

Buggy python submission (verdict: Runtime Error):
x=int(input())

for i in range(-118,120):
  for j in range(-118,120):
    if i**2-j**2==x:
      print(i,j)
      exit(1)


Fixed submission:
x=int(input())
# an = n^5 - (n - 1)^5
# a -> 120~-119 -> -118~119
# b -> 119~-120 -> -119~118
for i in range(-118,120):
  for j in range(-119,119):
    if i**5-j**5==x:
      print(i,j)
      exit()
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
mList=[int(input()) for i in range(m)]

#dp=[0]*(n+1)
dp=[-1]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

#for i in range(2,n+1):
#  if i in mList: continue
#  dp[i]+=dp[i-1]
#  dp[i]+=dp[i-2]
#  dp[i]%=1000000007

def calc(i):
  if dp[i]!=-1: return dp[i]
  if i in mList:
    dp[i]=0
    return dp[i]
  dp[i]=calc(i-1)+calc(i-2)
  dp[i]%=1000000007
  return dp[i]

print(calc(n))
#print(dp[n])


Fixed submission:
n,m=map(int,input().split())
mList=set([int(input()) for _ in range(m)])

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
mList=[int(input()) for i in range(m)]

dp=[0]*(n+1)
#dp=[-1]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

#def calc(i):
#  if dp[i]!=-1: return dp[i]
#  if i in mList:
#    dp[i]=0
#    return dp[i]
#  dp[i]=calc(i-1)+calc(i-2)
#  dp[i]%=1000000007
#  return dp[i]

#print(calc(n))
print(dp[n])


Fixed submission:
n,m=map(int,input().split())
mList=set([int(input()) for _ in range(m)])

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

print(dp[n])

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
mList=[int(input()) for i in range(m)]

dp=[-1]*(n+1)
dp[0]=1

def calc(i):
  if dp[i]!=-1: return dp[i]
  if i in mList:
    dp[i]=0
    return dp[i]
  if i==1:
    dp[i]=calc(i-1)
    return dp[i]
  dp[i]=calc(i-1)+calc(i-2)
  return dp[i]

print(calc(n)%1000000007)


Fixed submission:
n,m=map(int,input().split())
mList=set([int(input()) for _ in range(m)])

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
mList=[int(input()) for i in range(m)]
n+=1

#dp=[float("inf")*n]
dp=[0]*n
#dp[0]=0
dp[0]=1
for i in range(1,n):
  #print(i,"に来る方法")
  if i in mList: continue
  dp[i]+=dp[i-1]
  #dp[i]=min(dp[i],dp[i-1]+abs(dp[i]-dp[i-1]))
  if i==1: continue
  dp[i]+=dp[i-2]
  #print(dp[i])
  #dp[i]=min(dp[i],dp[i-2]+abs(dp[i]-dp[i-2]))

print(dp[n-1]%1000000007)

Fixed submission:
n,m=map(int,input().split())
mList=set([int(input()) for _ in range(m)])

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

print(dp[n])
Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    #print("i=",i,"j=",j)
    #dp[i][j]=max(dp[i][j],dp[i-1][j])
    #if j-w[i]<0: continue
    #dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
    if j-w[i]<0:
      dp[i][j]=max(dp[i][j],dp[i-1][j])
    else:
      dp[i][j]=max(dp[i][j],dp[i-1][j],dp[i-1][j-w[i]]+v[i])

#print(dp)
print(dp[N][W])


Fixed submission:
N,W=map(int,input().split())
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    #print("i=",i,"j=",j)
    dp[i][j]=max(dp[i][j],dp[i-1][j])
    if j-w[i]<0: continue
    dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])

#print(dp)
print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    #print("i=",i,"j=",j)
    dp[i][j]=max(dp[i][j],dp[i-1][j])
    if j-w[i]<0: continue
    dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])

#print(dp)
print(dp[N][W])


Fixed submission:
N,W=map(int,input().split())
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    #print("i=",i,"j=",j)
    dp[i][j]=max(dp[i][j],dp[i-1][j])
    if j-w[i]<0: continue
    dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])

#print(dp)
print(dp[N][W])
Buggy python submission (verdict: Runtime Error):
def main():
    n=int(input())
    a=list(map(int,input().split()))
    if 0 in a:
        print(0)
        return
    ans=1
    for i in a:
        ans=ans*i
        if pro>1000000000000000000:
            print(-1)
            return    
    print(ans)
    return
main()            

Fixed submission:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    if 0 in a:
        print(0)
        return
    ans=1
    for i in a:
        ans=ans*i
        if ans>1000000000000000000:
            print(-1)
            return    
    print(ans)
    return
main()

Buggy python submission (verdict: Runtime Error):
def main():
    n=int(input())
    a=list(map(int,input().split()))
    if 0 in a:
        print(0)
        return
    ans=1
    for i in a:
        pro=pro*i
        if pro>1000000000000000000:
            print(-1)
            return    
    print(ans)
    return
main()            

Fixed submission:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    if 0 in a:
        print(0)
        return
    ans=1
    for i in a:
        ans=ans*i
        if ans>1000000000000000000:
            print(-1)
            return    
    print(ans)
    return
main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

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

a_sorted = sorted(A, key=lambda x: -x)

circle = [a_sorted[0]]
ans = 0
for a in a_sorted:
    tmp = 0
    tmp_idx = -1
    for i in range(len(circle) - 1):
        cand = min(circle[i], circle[i + 1])
        if cand > tmp:
            tmp = cand
            tmp_idx = i
    ans += tmp
    circle.insert(tmp_idx + 1, a)

print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

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

a_sorted = sorted(A, key=lambda x: -x)

circle = [a_sorted[0]]
ans = 0
for idx, a in enumerate(a_sorted[1:]):
    ans += circle[idx]
    circle.extend([a, a])

print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

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

th = sum(A) // (4 * M)

sorted_A = sorted(A, key=lambda x: -x)
if sorted_A[M] < th:
    print("No")
else:
    print("Yes")


Fixed submission:
# -*- coding: utf-8 -*-

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

th = 1.0 * sum(A) / (4 * M)

sorted_A = sorted(A, key=lambda x: -x)
if sorted_A[M - 1] < th:
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def lcm_base(x, y):
    return ((x * y) // fractions.gcd(x, y))


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


min_AB = lcm(*A)

ans = 0
for a in A:
    ans += min_AB // a

print(ans % mod)


Fixed submission:
# -*- coding: utf-8 -*-

import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def lcm_base(x, y):
    return ((x * y) // fractions.gcd(x, y))


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


min_AB = lcm(*A)

ans = 0
for a in A:
    ans += min_AB // a

print(ans % mod)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0] * M
keys = [0] * M
inf = 10 ** 12
for i in range(M):
    a[i], _ = map(int, input().split())
    c_list = list(map(int, input().split()))
    keys[i] = sum([2 ** j for j in range(N) if j + 1 in c_list])

dp = [inf] * (N ** 2)
dp[0] = 0

# print(keys)

for i in range(M):  # use key i
    for j in range(N ** 2):
        dp[j | keys[i]] = min(dp[j] + a[i], dp[j | keys[i]])
        # print(dp, j, keys[i], dp[j | keys[i]], dp[j], a[i])

ans = dp[-1]
if ans == inf:
    ans = -1
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0] * M
keys = [0] * M
inf = 10 ** 12
for i in range(M):
    a[i], _ = map(int, input().split())
    c_list = list(map(int, input().split()))
    keys[i] = sum([2 ** j for j in range(N) if j + 1 in c_list])

dp = [inf] * (2 ** N)
dp[0] = 0

# print(keys)

for i in range(M):  # use key i
    for j in range(2 ** N):
        # print(dp, j, keys[i], dp[j | keys[i]], dp[j], a[i])
        dp[j | keys[i]] = min(dp[j] + a[i], dp[j | keys[i]])

ans = dp[-1]
if ans == inf:
    ans = -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
ab = [None] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

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

ans = [0] * N
ans[0] = px_n[0]
for i in range(N - 1):
    a, b = ab[i]
    ans[b-1] += ans[a-1] + px_n[b-1]

print(*ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
ab = [None] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

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

ans = [0] * N
ans[0] = px_n[0]
for (a, b) in ab:
    ans[b-1] += ans[a-1] + px_n[b-1]

print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
ab = [None] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

px = [None] * Q
for i in range(Q):
    px[i] = list(map(int, input().split()))
px = sorted(px, key=lambda x: (x[0], x[1]))

ans = [0] * N
ans[0] = sum([x for (p, x) in px if p == 1])
for i in range(N - 1):
    a, b = ab[i]
    ans[b-1] += ans[a-1] + sum([x for (p, x) in px if p == b])

print(*ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
ab = [None] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

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

ans = [0] * N
ans[0] = px_n[0]
for (a, b) in ab:
    ans[b-1] += ans[a-1] + px_n[b-1]

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

s = input()
t = input()

if not set(t) <= set(s):
    print(-1)
    exit()

repeat = 0
s_idx = 0
for c in t:
    idx = s[s_idx:].find(c)
    if idx == -1:
        idx = s.find(c)
        repeat += 1
    else:
        idx = idx + s_idx
    s_idx = idx + 1
else:
    ans = repeat * len(s) + s_idx

print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

from bisect import bisect_left

s = input()
t = input()

if not set(t) <= set(s):
    print(-1)
    exit()

s_dict = {}
for i in range(len(s)):
    c = s[i]
    if c not in s_dict.keys():
        s_dict[c] = [i]
    else:
        s_dict[c].append(i)

repeat = 0
s_idx = 0
for c in t:
    idx = bisect_left(s_dict[c], s_idx)
    if idx == len(s_dict[c]):
        s_idx = s_dict[c][0] + 1
        repeat += 1
    else:
        s_idx = s_dict[c][idx] + 1
else:
    ans = repeat * len(s) + s_idx

print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N = int(input())
A = [None] * N
for i in range(N):
    A[i] = int(input())

max_list = [-1]

for i in range(N):
    ok_list = [i for i, x in enumerate(max_list) if x < A[i]]
    if ok_list:
        max_list[ok_list[0]] = A[i]
    else:
        max_list.append(A[i])

ans = len(max_list)
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

r = int(input())

ans = 3 * r * r

print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

x, a = int(input()), int(input())

if x < a:
    print("0")
else:
    print("10")


Fixed submission:
# -*- coding: utf-8 -*-

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

if x < a:
    print("0")
else:
    print("10")
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

lst = [0]
count = 0
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        count += 1
    lst = lst + [count]

for l, r in LR:
    ans = lst[r-1] - lst[l-1]
    print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

lst = [0] * N
count = 0
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        count += 1
    lst[i + 1] = count

for l, r in LR:
    ans = lst[r-1] - lst[l-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

lst = [0]
count = 0
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        count += 1
    lst = lst + [count]

for l, r in LR:
    ans = lst[r-1] - lst[l-1]
    print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

lst = [0] * N
count = 0
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        count += 1
    lst[i + 1] = count

for l, r in LR:
    ans = lst[r-1] - lst[l-1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import numpy as np

N, M, C = map(int, input().split())
B = np.ndarray([M, 1])
B = list(map(int, input().split()))
A = np.ndarray([N, M])
for i in range(N):
    A[i, :] = list(map(int, input().split()))

ans = sum((A @ B + C) > 0)

print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import numpy as np

N, M, C = map(int, input().split())
B = np.ndarray([M, 1])
B = list(map(int, input().split()))
A = np.ndarray([N, M])
for i in range(N):
    A[i, :] = list(map(int, input().split()))

ans = sum((np.dot(A,B) + C) > 0)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import re

S = input()

s = S
ans = 0
while 1:
    s, t = re.subn("01|10", "", s)
    ans += t * 2
    if t == 0:
        break

print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

S = input()

ans = min(S.count('0'), S.count('1'))
print(ans*2)