Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if ais[0]==1:
  dp[1]=0
  ais.pop(0)
else:
  dp[1]=1
for i in range(2,n+1):
    if len(ais)>0 and ais[0]==i:
        dp[i] = 0
        ais.pop(0)
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)


Fixed submission:
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if len(ais)>0 and ais[0]==1:
  dp[1]=0
  ais.pop(0)
else:
  dp[1]=1
for i in range(2,n+1):
    if len(ais)>0 and ais[0]==i:
        dp[i] = 0
        ais.pop(0)
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if 1 in ais:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n+1):
    if i in ais:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

Fixed submission:
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if len(ais)>0 and ais[0]==1:
  dp[1]=0
  ais.pop(0)
else:
  dp[1]=1
for i in range(2,n+1):
    if len(ais)>0 and ais[0]==i:
        dp[i] = 0
        ais.pop(0)
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n = map(int, input().split())
ans = 0
rgb = sorted([r,g,b])
n_rgb = []
for e in rgb:
  n_rgb.append(n//e)
for i in range(n_rgb[2]+1):
  for j in range(n_rgb[1]+1):
    N = n - i*rgb[2] - j*rgb[1]
    if  N>=0 and N%rgb[0]==0:
      ans+=1
      
print(ans)

Fixed submission:
r,g,b,n = map(int, input().split())
ans = 0
rgb = sorted([r,g,b])
n_rgb = []
for e in rgb:
  n_rgb.append(n//e)
for i in range(n_rgb[2]+1):
  N2 = n-i*rgb[2]
  for j in range(n_rgb[1]+1):
    N = N2 - j*rgb[1]
    if  N>=0 and N%rgb[0]==0:
      ans+=1
      
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ac = []
for i in range(n-1):
  if s[i:i+2] == "AC":
    ac.append(1)
  else:
    ac.append(0)
for j in range(q):
  l,r = map(int, input().split())
  if r == q:
    r -= 1
  ls = ac[l-1:r-1]
  print(ls.count(1))


Fixed submission:
n, q = map(int, input().split())
s = input()
ac = [0] * (n+1)
for i in range(n):
  if s[i:i+2] == "AC":
    ac[i+1] = ac[i] + 1
  else:
    ac[i+1] = ac[i]
for j in range(q):
  l,r = map(int, input().split())
  print(ac[r-1]-ac[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ac = []
for i in range(n-1):
  if s[i:i+2] == "AC":
    ac.append(1)
  else:
    ac.append(0)
for j in range(q):
  l,r = map(int, input().split())
  if r == q:
    r -= 1
  ls = ac[l-1:r-1]
  print(sum(ls))


Fixed submission:
n, q = map(int, input().split())
s = input()
ac = [0] * (n+1)
for i in range(n):
  if s[i:i+2] == "AC":
    ac[i+1] = ac[i] + 1
  else:
    ac[i+1] = ac[i]
for j in range(q):
  l,r = map(int, input().split())
  print(ac[r-1]-ac[l-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
ais = list(map(int, input().split()))
a_mini = ais[0]
a_max = ais[0]
for i in rnage(1, n):
  if ais[i] < a_mini:
    a_mini = ais[i]
  if ais[i] > a_max:
    a_max = ais[i]
print(a_max - a_mini)

Fixed submission:
n = int(input())
ais = list(map(int, input().split()))
ais_sort = sorted(ais)
print(ais_sort[n-1] - ais_sort[0])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
X = list(map(int,input().split()))
h = int(n/2)
for i in range(n):
  xis = []
  if i != 0:
    xis += X[0:i]
    xis += X[i+1:n]
    print(sorted(xis)[h-1])
  else:
    xis = X[1:]
    print(sorted(xis)[h-1])

Fixed submission:
n = int(input())
X = list(map(int,input().split()))
h = int(n/2)
Xs = sorted(X)
m1 = Xs[h-1]
m2 = Xs[h]

for i in range(n):
  if X[i] <= m1:
    print(m2)
  else:
    print(m1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ais = input().split()
ais_sort = sort(ais)
alice = 0
bob = 0
if n % 2 == 0:
  for i in range(n):
    if i % 2 == 1:
      alice += int(ais_sort[i])
    else:
      bob += int(ais_sort[i])
else:
  for j in range(n):
    if i % 2 == 0:
      alice += int(ais_sort[i])
    else:
      bob += int(ais_sort[i])
print(alice - bob)

Fixed submission:
n = int(input())
ais = input().split()
ais_int = [int(a) for a in ais]
ais_sort = ais_int.sort()
alice = 0
bob = 0
if n % 2 == 0:
  for i in range(n):
    if i % 2 == 1:
      alice += int(ais_int[i])
    else:
      bob += int(ais_int[i])
else:
  for j in range(n):
    if j % 2 == 0:
      alice += int(ais_int[j])
    else:
      bob += int(ais_int[j])
print(alice - bob)
Buggy python submission (verdict: Runtime Error):
m = 0
if len(ss) <= len(ts):
  m = len(ss)
  l = 0
  for j in range(m):
    if alph.index(ss[j]) < alph.index(ts[j]):
      print("Yes")
      break
    elif alph.index(ss[j]) == alph.index(ts[j]) :
      if j == m -1:
        print("Yes")
      else:
        pass
    else:
      print("No")
      break
elif len(ss) == len(ts):
  m = len(ss)
  l = 0
  for j in range(m):
    if alph.index(ss[j]) < alph.index(ts[j]):
      print("Yes")
      break
    elif alph.index(ss[j]) == alph.index(ts[j]) :
      if j == m -1:
        print("No")
      else:
        pass
    else:
      print("No")
      break
else:
  m = len(ts)
  l = 0
  for j in range(m):
    if alph.index(ss[j]) < alph.index(ts[j]):
      print("Yes")
      break
    elif alph.index(ss[j]) == alph.index(ts[j]) :
      if j == m - 1:
        print("No")
    else:
      print("No")
      break

Fixed submission:
s = input()
t = input()
sl = list(s)
tl = list(t)
sl_asc = sorted(sl)
tl_desc = sorted(tl, reverse=True)
s2 = ''.join(sl_asc)
t2 = ''.join(tl_desc)
if s2 < t2:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

n = int(input())
print(int((n - 1) / 2) if n % 2 == 1 else int(n / 2) - 1)


Fixed submission:
#!/usr/bin/env python3
# https://atcoder.jp/contests/abc134/tasks/abc134_b

import math
n, d = [int(x) for x in input().split()]
print(math.ceil(n / (d * 2 + 1)))
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc093/tasks/abc093_b
a, b, k = [int(x) for x in input().split()]
r = list(range(a, b + 1))
for v in sorted(set(r[:k] + r[-k:])):
    print(v)


Fixed submission:
# https://atcoder.jp/contests/abc093/tasks/abc093_b
a, b, k = [int(x) for x in input().split()]
s = list(range(a, b + 1)[:k])
t = list(range(a, b + 1)[-k:])
for v in sorted(set(s + t)):
    print(v)

Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc093/tasks/abc093_b
a, b, k = [int(x) for x in input().split()]
r = list(range(a, b + 1))
for v in sorted(set(r[:k] + r[-k:])):
    print(v)


Fixed submission:
# https://atcoder.jp/contests/abc093/tasks/abc093_b
a, b, k = [int(x) for x in input().split()]
s = list(range(a, b + 1)[:k])
t = list(range(a, b + 1)[-k:])
for v in sorted(set(s + t)):
    print(v)
Buggy python submission (verdict: Runtime Error):
n=int(input())
d=[int(input()) for _ in range(n)]
print(len(set(sorted(d))))

Fixed submission:
s=input()
print(s.replace("2017","2018"))
Buggy python submission (verdict: Time Limit Exceeded):
n,y=[int(x) for x in input().split()]
for i in range(y//10000,-1,-1):
    for j in range((y-10000*i)//5000,-1,-1):
        for k in range((y-10000*i-5000*j)//1000,-1,-1):
            if i+j+k==n and i*10000+j*5000+k*1000==y:
                print(i,j,k)
                exit()
print("-1 -1 -1")


Fixed submission:
n,y=[int(x) for x in input().split()]
for i in range(y//10000,-1,-1):
    for j in range((y-10000*i)//5000,-1,-1):
        if (n-i-j)*1000==(y-i*10000-j*5000):
            print(i,j,n-i-j)
            exit()
print("-1 -1 -1")
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

n = int(input())
d = [int(x) for x in input().split()]
m = int(input())
t = [int(x) for x in input().split()]
for et in t:
    if et not in d:
        print("NO")
        exit()
    d.remove(et)
print("YES")


Fixed submission:
#!/usr/bin/env python3

import collections
n = int(input())
d = collections.Counter([int(x) for x in input().split()])
m = int(input())
t = collections.Counter([int(x) for x in input().split()])
for k, v in t.items():
    if d[k] < v:
        print("NO")
        exit()
print("YES")
Buggy python submission (verdict: Time Limit Exceeded):
g = [[] for _ in range(int(input()))]
for gv in g:
    gv.append(int(input()) - 1)

q = [[0]]
while q:
    path = q.pop(0)
    n = path[-1]
    if n == 1:
        print(len(path) - 1)
        exit()
    else:
        for x in g[n]:
            if x not in path:
                new_path = path[:]
                new_path.append(x)
                q.append(new_path)
print(-1)

Fixed submission:
n=int(input())
a = [int(input()) for x in [0]*n]
k=0
for i in range(n):
    if k==1:
        print(i)
        break
    k=a[k]-1
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

n = int(input())
a = [int(x) for x in input().split()]
c = 0
b = [{i + 1, x} for i, x in enumerate(a)]
for i, e in enumerate(sorted(b)):
    if b.count(e) == 2:
        c += 1
print(c // 2)


Fixed submission:
#!/usr/bin/env python3

n = int(input())
a = [int(x) for x in input().split()]
c = 0
for i, ax in enumerate(a):
    if a[ax - 1] == i + 1:
        c += 1
print(c // 2)
Buggy python submission (verdict: Runtime Error):
a,b,c=[int(x) for x in input().split()]
print("YES") if sorted([a,b,c]) == [5,5,7] else print("NO")

Fixed submission:
a,b,c=[int(x) for x in input().split()]
print("YES") if sorted([a,b,c]) == [5,5,7] else print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

dic = dict()

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

# dic = sorted(dic.items(), key=lambda x:x[0])

max_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]

max_list.sort()

for lis in max_list:
  print(lis)


Fixed submission:
N = int(input())

s = [None for _ in range(N)]

for i in range(N):
  s[i] = input()

s.sort()

max_list = []
max_v = 1

count = 1
prev = s[0]


for i in range(1, N):
  # print(s[i], prev, count)
  if s[i] == prev:
    count += 1
  else:
    if max_v == count:
      max_list.append(prev)
    elif max_v < count:
      max_list = [prev]
      max_v = count
    count = 1
    prev = s[i]


if max_v == count:
  max_list.append(prev)
elif max_v < count:
  max_list = [prev]
  max_v = count

for k in max_list:
  print(k)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

Ss = [None for _ in range(N)]

dic = dict()

for i in range(N):
  Ss[i] = input()

for s in Ss:
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

# dic = sorted(dic.items(), key=lambda x:x[0])

max_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]

max_list.sort()

for lis in max_list:
  print(lis)


Fixed submission:
N = int(input())

s = [None for _ in range(N)]

for i in range(N):
  s[i] = input()

s.sort()

max_list = []
max_v = 1

count = 1
prev = s[0]


for i in range(1, N):
  # print(s[i], prev, count)
  if s[i] == prev:
    count += 1
  else:
    if max_v == count:
      max_list.append(prev)
    elif max_v < count:
      max_list = [prev]
      max_v = count
    count = 1
    prev = s[i]


if max_v == count:
  max_list.append(prev)
elif max_v < count:
  max_list = [prev]
  max_v = count

for k in max_list:
  print(k)
Buggy python submission (verdict: Time Limit Exceeded):
def sums(N):
  return 1 + (N-1) * 0.5

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

exp = [0 for _ in range(N)]
for i in range(0, N):
  exp[i] = sums(Ps[i])

ans = [0 for _ in range(N)]

for i in range(0, K):
  ans[K-1] += exp[i]

for i in range(K, N):
  ans[i] = max(ans[i-1], sum(exp[i+1-K:i+1]))


print(ans[N-1])


Fixed submission:
def sums(N):
  return 1 + (N-1) * 0.5

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

exp = [0 for _ in range(N)]
for i in range(0, N):
  exp[i] = sums(Ps[i])

summed = [0 for _ in range(N)]
summed[0] = exp[0]

for i in range(1, N):
  summed[i] = summed[i-1] + exp[i]

max_i=summed[K-1]

for i in range(K, N):
  max_i = max(max_i, summed[i]-summed[i-K])

print(max_i)

Buggy python submission (verdict: Time Limit Exceeded):
def sums(N):
  res = 0
  for i in range(1, N+1):
    res += i
  return res

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



exp = [0 for _ in range(N)]
for i in range(0, N):
  exp[i] = sums(Ps[i])/Ps[i]

ans = [0 for _ in range(N)]

for i in range(0, K):
  ans[K-1] += exp[i]

for i in range(K, N):
  ans[i] = max(ans[i-1], sum(exp[i+1-K:i+1]))


print(ans[N-1])


Fixed submission:
def sums(N):
  return 1 + (N-1) * 0.5

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

exp = [0 for _ in range(N)]
for i in range(0, N):
  exp[i] = sums(Ps[i])

summed = [0 for _ in range(N)]
summed[0] = exp[0]

for i in range(1, N):
  summed[i] = summed[i-1] + exp[i]

max_i=summed[K-1]

for i in range(K, N):
  max_i = max(max_i, summed[i]-summed[i-K])

print(max_i)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False
input = sys.stdin.readline
Xs = input()
X = int(Xs)
X_ = int(Xs[-3:])
_X = int(Xs[0:-3])
if X < 100:
  print("0")
  exit()
if X_ == 0 or X_ == 1 or X_ == 2 or X_ == 3 or X_ == 4 or X_ == 5:
  print("1")
  exit()
count = 0
count += X_ // 5
X_ = X_ %  5
count += X_ //4
X_=X_%4
count += X_ //3
X_=X_%3
count += X_ //2
X_=X_%2
count += X_ //1
X_=X_%1
if _X - count >= 0:
  print("1")
else:
  print("0")
if em: sys.stdin = open('/dev/tty')


Fixed submission:
#!/usr/bin/env python3
import sys
args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False
input = sys.stdin.readline
Xs = input()
X = int(Xs)
if X < 100:
  print("0")
  exit()
X_ = int(Xs[-3:])
_X = int(Xs[0:-3])
if X_ == 0 or X_ == 1 or X_ == 2 or X_ == 3 or X_ == 4 or X_ == 5:
  print("1")
  exit()
count = 0
count += X_ // 5
X_ = X_ %  5
count += X_ //4
X_=X_%4
count += X_ //3
X_=X_%3
count += X_ //2
X_=X_%2
count += X_ //1
X_=X_%1
if _X - count >= 0:
  print("1")
else:
  print("0")
if em: sys.stdin = open('/dev/tty')
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False
input = sys.stdin.readline
a, b, x = map(int, input().split())
import math
if 2*x/b <= a:
  ans = math.degrees(math.atan(a*b**2/(2*x)))
else:
  ans = 90 - math.degrees(math.atan(a/(2*b - 2*x/(a**2))))
print(ans)
if em: sys.stdin = open('/dev/tty')


Fixed submission:
#!/usr/bin/env python3
import sys
args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False
input = sys.stdin.readline
a, b, x = map(int, input().split())
if a**2*b == x:
  print(0)
  exit()
import math
if 2*x <= a**2*b:
  t1 = a*b**2
  t2 = 2*x
  ans = math.degrees(math.atan(t1/t2))
else:
  t1 = a**3
  t2 = 2*a**2*b - 2*x
  ans = 90 - math.degrees(math.atan(t1/t2))
print(ans)
if em: sys.stdin = open('/dev/tty')
Buggy python submission (verdict: Runtime Error):
step = input()

ng = ["L", "R"]

for i in range(0, len(step)):
  if step[i] == ng[i%2]:
    return "No"
return "Yes"


Fixed submission:
step = input()

ng = ["L", "R"]

for i in range(0, len(step)):
  if step[i] == ng[i%2]:
    print("No")
    exit()
print("Yes")
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
from IPython import embed

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

A = []
for i in range(0, Q):
  A.append(int(input()))

wins = [0] * N
for i in A:
  wins[i - 1] = wins[i - 1] + 1

# sys.stdin = open('/dev/tty')
# embed()

for i in range(0, N):
  score = K - Q + wins[i]
  if score > 0:
    print("Yes")
  else:
    print("No")


Fixed submission:
#!/usr/bin/env python3

import sys
# from IPython import embed

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

A = []
for i in range(0, Q):
  A.append(int(input()))

wins = [0] * N
for i in A:
  wins[i - 1] = wins[i - 1] + 1

# sys.stdin = open('/dev/tty')
# embed()

for i in range(0, N):
  score = K - Q + wins[i]
  if score > 0:
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

#### input
N = int(input())
# a, b = map(int, input().split())
# a = list(map(int, input().split()))
# a = list(map(lambda x: int(x)*(-1), a))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')

#### function
# @lru_cache(maxsize=10000)

#### process
I = [i for i in range(1, N+1)]
P = [i for i in range(2, N+1)]
P.append(1)

rems = [I[i] % P[i] for i in range(0, len(I))]
print(sum(rems))
# if em: embed()

## heapsort, O(NlogN)
# import heapq
# heapq.heapify(A)
# min = heapq.heappop(A)
# heapq.heappush(A, new_element)


Fixed submission:
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

#### input
N = int(input())
# a, b = map(int, input().split())
# a = list(map(int, input().split()))
# a = list(map(lambda x: int(x)*(-1), a))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')

#### function
# @lru_cache(maxsize=10000)

#### process

if N % 2 == 0:
  tmp = int(N/2)
  print(int(tmp*(N-1)))
else:
  tmp = int((N-1)/2)
  print(int(tmp*N))

# I = [i for i in range(1, N+1)]
# P = [i for i in range(2, N+1)]
# P.append(1)

# rems = [I[i] % P[i] for i in range(0, len(I))]
# print(sum(rems))

# if em: embed()

## heapsort, O(NlogN)
# import heapq
# heapq.heapify(A)
# min = heapq.heappop(A)
# heapq.heappush(A, new_element)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import cupy
import sys
from operator import itemgetter
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)


input = sys.stdin.readline
#### input
N, Q = list(map(int, input().split()))
ABs = [None]*(N-1)
for i in range(0, N-1):
  ABs[i] = list(map(int, input().split()))

ABs.sort(key=itemgetter(0))

PXs = [None]*Q
for i in range(0, Q):
  PXs[i] = list(map(int, input().split()))
# a = list(map(int, input().split()))
# required_list = list(map(lambda x: int(x)*(-1), target_list))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')
#### class
# class Node:
#   def __init__(self, data):
#     self.data = data
#     self.child= []
#     self.below = []

#### function
# @lru_cache(maxsize=10000)

#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]

for AB in ABs:
  above_nodes[AB[1]-1].extend(above_nodes[AB[0]-1])

for PX in PXs:
  scores[PX[0]-1] = scores[PX[0]-1] + PX[1]

node_scores = [None] * N
for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  node_scores[i] = node_score
print(' '.join(map(str, node_scores)))

# if em: embed()
## heapsort, O(NlogN)
# import heapq
# As = [0,1,2,3]
# heapq.heapify(As)
# min = heapq.heappop(As)
# heapq.heappush(As, inserted_element)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
# 遅延評価で加えてあげるだけ
 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))
 
answer = ' '.join(map(str,value[1:]))
print(answer)
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
W = []
V = []

for _ in range(N):
  w, v = map(int, input().split())
  W.append(w)
  V.append(v)

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

for i in range(W+1):
  if i >= W[0]
  Ans[0][i] = V[0]

for i in range(1, N):
  for w in range(W+1):
    if w - W[i] >= 0:
      Ans[i][w] = max(Ans[i-1][w-W[i]], Ans[i-1][w], Ans[i][w])
    else:
      Ans[i][w] = max(Ans[i-1][w], Ans[i][w])

print(max(Ans[N-1]))


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

N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:
      # pdb.set_trace()
      # print(num, load, ws[num], vs[num])
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:
      Value[num][load] = max(Value[num][load], Value[num-1][load])

print(Value[N-1][W])

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
W = []
V = []

for _ in range(N):
  w, v = map(int, input().split())
  W.append(w)
  V.append(v)

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

for i in range(W+1):
  if i >= W[0]
  Ans[0][i] = V[0]

for i in range(1, N):
  for w in range(W+1):
    Ans[i][w] = max(Ans[i-1][w-W[i]], Ans[i-1][w])

print(max(Ans[N-1]))

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

N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:
      # pdb.set_trace()
      # print(num, load, ws[num], vs[num])
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:
      Value[num][load] = max(Value[num][load], Value[num-1][load])

print(Value[N-1][W])
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

As = []
for _ in range(H):
  As.append(input())
paths = [[0 for _ in range(W)] for _ in range(H)]

paths[0][0] = 1

mod = 1e+9 + 7

for width in range(W):
  for height in range(H):
    if As[height][width] == "#":
      # 壁のマスであればスキップする
      continue
    if height < H-1:
      if As[height + 1][width] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height + 1][width] += paths[height][width]
    if width < W-1:
      if As[height][width + 1] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height][width + 1] += paths[height][width]

print(int(paths[H-1][W-1] % mod))


Fixed submission:
H, W = map(int, input().split())

As = []
for _ in range(H):
  As.append(input())
paths = [[0 for _ in range(W)] for _ in range(H)]

paths[0][0] = 1

mod = 1e+9 + 7

for width in range(W):
  for height in range(H):
    if As[height][width] == "#":
      # 壁のマスであればスキップする
      continue
    if height < H-1:
      if As[height + 1][width] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height + 1][width] = int((paths[height + 1][width] + paths[height][width]) % mod)
    if width < W-1:
      if As[height][width + 1] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height][width + 1] = int((paths[height][width + 1] + paths[height][width]) % mod)

print(paths[H-1][W-1])