Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n, q = [int(i) for i in input().split()]
s = input()
positions = []

for i in range(1, n+1):
    if s[(i-1):(i+1)] == 'AC':
        positions.append(i)

for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(len([i for i in positions if i in range(l, r)]))


Fixed submission:
import bisect

n, q = [int(i) for i in input().split()]
s = input()
positions = []

for i in range(1, n+1):
    if s[(i-1):(i+1)] == 'AC':
        positions.append(i)

for i in range(q):
    l, r = [int(i) for i in input().split()]
    l_index = bisect.bisect_left(positions, l)
    r_index = bisect.bisect_left(positions, r)
    print(r_index - l_index)

Buggy python submission (verdict: Time Limit Exceeded):
n, q = [int(i) for i in input().split()]
s = input()
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(s[(l-1):r].count('AC'))


Fixed submission:
import bisect

n, q = [int(i) for i in input().split()]
s = input()
positions = []

for i in range(1, n+1):
    if s[(i-1):(i+1)] == 'AC':
        positions.append(i)

for i in range(q):
    l, r = [int(i) for i in input().split()]
    l_index = bisect.bisect_left(positions, l)
    r_index = bisect.bisect_left(positions, r)
    print(r_index - l_index)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(sum([ i for i in range(1, N)]))

Fixed submission:
N = int(input())
print(N*(N-1)//2)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
answer = 0
print(sum([ i % (i + 1) for i in range(1, N)]))

Fixed submission:
N = int(input())
print(N*(N-1)//2)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
answer = 0
for i in range(1, N):
  answer +=  i % (i + 1)
  
print(answer)

Fixed submission:
N = int(input())
print(N*(N-1)//2)
Buggy python submission (verdict: Runtime Error):
S = input()
List = [input() for i in range(1)]
T = List[0]

Slst = list(S)
Tlst = list(T)
M = 0

for x in range(3):
    if Slst[x] == Tlst[x]:
        M += 1
print(M)


Fixed submission:
lst = [int(x) for x in input().split()]
A = lst[0]
B = lst[1]

if B >= 2:
    m = 0
    while (A-1) * m + 1 < B:
        m += 1
    print(m)

if B == 1:
    print(0)
Buggy python submission (verdict: Runtime Error):
N,k=map(int,input().split())
R=N-k
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
    
for i in range(1,k+1):
  a= cmb(k-1,i-1)
  b= cmb(R+1,i)
  print(a*b)

Fixed submission:
s=list(input())
a='No'
if s[1]==s[2] and s[3]==s[0] and s[1]!=s[3] and s[1]!=s[0]:
  a='Yes'
elif s[1]==s[3] and s[2]==s[0] and s[1]!=s[2] and s[1]!=s[0]:
  a='Yes'
elif s[1]==s[0] and s[2]==s[3] and s[1]!=s[2] and s[1]!=s[3]:
  a='Yes'
print(a)
Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
li=list(int,map(input().split()))
d=0
c=1
for l in li:
  	d=d+l
	if d>x:
		break
	
	c=c+1
print(c)

Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
li=list(map(input().split()))
d=0
c=1
for l in li:
  	d=d+l
	if d>x:
		break
	
	c=c+1
print(c)


Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
li=map(input().split())
d=0
c=1
for l in li:
  	d=d+l
	if d>x:
		break
	
	c=c+1
	
print(c)


Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
li=input().split()
d=0
c=0
for l in li:
	if d>x:
		break
	d=d+l
	c=c+1
	
print(c)


Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
x, a=map(int, input().split())
if	x < a
	l = 0
else
	l = 10
print(l)

Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
x, a=map(int, input().split())
if	x < a
	l = 0
else
	l = 10
print (l)   

Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
x, a=map(int, input().split())
if	x < a
	l = 0
if x >= a
	l = 10
print (l)   

Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
x,a=map(int,input().split())
if	x < a
	l = 0
if x >= a
	l = 10
print (l)   

Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)

Buggy python submission (verdict: Runtime Error):
x,a=map(int,input()split())
if	x<a
	l=0
if x>=a
	l=10
print (l)   

Fixed submission:
x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)
Buggy python submission (verdict: Runtime Error):
N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
count = 0
for j in range(1, N):
  if H[j] <= H[j-1]:
  	count += 1
  	if j == N-1:
      if count > m_max:
      	m_max = count
  else:
    if count > m_max:
      m_max = count
    count = 0
print(m_max)

Fixed submission:
N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
count = 0
for j in range(1, N):
  if H[j] <= H[j-1]:
    count += 1
    if j == N-1:
      if count > m_max:
        m_max = count
  else:
    if count > m_max:
      m_max = count
    count = 0
print(m_max)

Buggy python submission (verdict: Runtime Error):
N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
count = 0
for j in range(1, N):
  if H[j] <= H[j-1]:
    count += 1
  	if j == N-1:
    	if count > m_max:
      		m_max = count
    	count = 0
  else:
    if count > m_max:
      m_max = count
    count = 0
print(m_max)

Fixed submission:
N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
count = 0
for j in range(1, N):
  if H[j] <= H[j-1]:
    count += 1
    if j == N-1:
      if count > m_max:
        m_max = count
  else:
    if count > m_max:
      m_max = count
    count = 0
print(m_max)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
for j in range(N-1):
  count = 0
  for k in range(j+1, N):
    if H[k] <= H[k-1]:
      count += 1
    else:
      break
  if count > m_max:
    m_max = count
print(m_max)

Fixed submission:
N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
count = 0
for j in range(1, N):
  if H[j] <= H[j-1]:
    count += 1
    if j == N-1:
      if count > m_max:
        m_max = count
  else:
    if count > m_max:
      m_max = count
    count = 0
print(m_max)
Buggy python submission (verdict: Runtime Error):
N = int(input())
v = map(int, input().split())
vv = map(float, v)
vv.sort()
ans = vv[0]
for i in range(1, len(vv)):
  ans = (ans + vv[i]) / 2
print(ans)

Fixed submission:
N = int(input())
v = [int(vi) for vi in input().split()]
vv = [float(vf) for vf in v]
vv.sort()
ans = vv[0]
for i in range(1, N):
  ans = (ans + vv[i]) / 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
H = [int(item) for item in input().split()]

cand = []
cand += [H[0], H[0] - 1]
for i in range(1, N):
    new_cand = []
    for c in cand:
        if c <= H[i] - 1:
            new_cand += [H[i], H[i] - 1]
        elif c == H[i]:
            new_cand += [H[i]]
    cand = new_cand
    if len(cand) == 0:
        print("No")
        break
else:
    print("Yes")


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

N = int(input())
H = [int(item) for item in input().split()]

cand = []
cand += [H[0], H[0] - 1]
for i in range(1, N):
    new_cand = []
    for c in cand:
        if c <= H[i] - 1:
            new_cand += [H[i], H[i] - 1]
        elif c == H[i]:
            new_cand += [H[i]]
    cand = list(set(new_cand))
    if len(cand) == 0:
        print("No")
        break
else:
    print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, K = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]

for v in range(max(A) + K, 0, -1):
    sum_m = []
    for a in A:
        sum_m.append(a % v)
    if sum(sum_m) % v == 0:
        if sum(sum_m) - max(sum_m) <= K:
            print(v)
            break


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

N, K = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


d_cand = make_divisors(sum(A))
d_cand.sort()
d_cand.reverse()

for d in d_cand:
    r = [a % d for a in A]
    rp_sum = sum(r)
    rm_sum = 0
    if rp_sum % d != 0:
        continue
    r.sort()

    for i in range(N):
        # index i まで r-, i+1から r+
        rp_sum -= r[i]
        rm_sum += r[i]

        n_min = max(0, -(rm_sum + rp_sum) / d + (N - i - 1))
        n_max = (K - rm_sum) / d
        if n_min <= n_max and (n_min % 1 == 0 or n_max % 1 == 0 or int(n_min) != int(n_max)):
            print(d)
            break
    else:
        continue
    break

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

N, K = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]

for v in range(sum(A), 0, -1):
    sum_m = []
    for a in A:
        sum_m.append(a % v)
    if sum(sum_m) % v == 0:
        if sum(sum_m) - max(sum_m) <= K:
            print(v)
            break


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

N, K = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


d_cand = make_divisors(sum(A))
d_cand.sort()
d_cand.reverse()

for d in d_cand:
    r = [a % d for a in A]
    rp_sum = sum(r)
    rm_sum = 0
    if rp_sum % d != 0:
        continue
    r.sort()

    for i in range(N):
        # index i まで r-, i+1から r+
        rp_sum -= r[i]
        rm_sum += r[i]

        n_min = max(0, -(rm_sum + rp_sum) / d + (N - i - 1))
        n_max = (K - rm_sum) / d
        if n_min <= n_max and (n_min % 1 == 0 or n_max % 1 == 0 or int(n_min) != int(n_max)):
            print(d)
            break
    else:
        continue
    break
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import math

N, M, K = [int(item) for item in input().split()]
mod = 10**9 + 7

total = 0
for d in range(1, N):
    score = (N - d) * M**2 * d
    score %= mod
    for i in range(2, K):
        score *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
        score %= mod
    total += score
    total %= mod

for d in range(1, M):
    score = (M - d) * N**2 * d
    score %= mod
    for i in range(2, K):
        score *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
        score %= mod
    total += score
    total %= mod


print(total)


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

N, M, K = [int(item) for item in input().split()]
mod = 10**9 + 7

score_c = 1
for i in range(2, K):
    score_c *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
    score_c %= mod

total = 0
for d in range(1, N):
    score = (N - d) * M**2 * d * score_c
    score %= mod
    total += score
    total %= mod

for d in range(1, M):
    score = (M - d) * N**2 * d * score_c
    score %= mod
    total += score
    total %= mod


print(total)
Buggy python submission (verdict: Runtime Error):
import re
import numpy as np
N, K = [int(item) for item in re.split(r"\s", input())]
S = [int(item) for item in list(input())]

if sum(S) == len(S) or sum(S) == 0:
    print(len(S))
else:
    S = S + [2]

    index = [-1]
    for i in range(N):
        if S[i] != S[i + 1]:
            index.append(i)

    count = np.diff(np.array(index)).tolist()

    # print(index)
    # print(count)

    cumsum = [0] + np.cumsum(count).tolist()
    c_len = len(cumsum)
    win = min(2 * K, c_len)
    if S[0] == 1:
        win += 1

    print(max([cumsum[i + win] - cumsum[i] for i in range(0, c_len - win, 2)]))


Fixed submission:
import re
import numpy as np
N, K = [int(item) for item in re.split(r"\s", input())]
S = [int(item) for item in list(input())]

if sum(S) == len(S) or sum(S) == 0:
    print(len(S))
else:
    S = S + [2]

    index = [-1]
    for i in range(N):
        if S[i] != S[i + 1]:
            index.append(i)

    count = np.diff(np.array(index)).tolist()

    if S[0] == 0:
        count = [0] + count
    if S[-2] == 0:
        count = count + [0]

    # print(index)
    #print("count", count)

    cumsum = [0] + np.cumsum(count).tolist()
    c_len = len(cumsum)
    win = min(2 * K + 1, c_len - 1)
    # print(cumsum)
    # print(win)

    print(max([cumsum[i + win] - cumsum[i] for i in range(0, c_len - win, 2)]))

Buggy python submission (verdict: Runtime Error):
import re
import numpy as np
N, K = [int(item) for item in re.split(r"\s", input())]
S = [int(item) for item in list(input())]

if sum(S) == len(S) or sum(S) == 0:
    print(len(S))
else:
    S = S + [2]

    index = [-1]
    for i in range(N):
        if S[i] != S[i + 1]:
            index.append(i)

    count = np.diff(np.array(index)).tolist()

    start = 0
    if S[0] == 0:
        start = 1

    # print(index)
    # print(count)

    cumsum = [0] + np.cumsum(count).tolist()
    c_len = len(cumsum)
    win = min(2 * K + 1, c_len - 1)
    print(max([cumsum[i + win] - cumsum[i] for i in range(start, c_len - win, 2)]))


Fixed submission:
import re
import numpy as np
N, K = [int(item) for item in re.split(r"\s", input())]
S = [int(item) for item in list(input())]

if sum(S) == len(S) or sum(S) == 0:
    print(len(S))
else:
    S = S + [2]

    index = [-1]
    for i in range(N):
        if S[i] != S[i + 1]:
            index.append(i)

    count = np.diff(np.array(index)).tolist()

    if S[0] == 0:
        count = [0] + count
    if S[-2] == 0:
        count = count + [0]

    # print(index)
    #print("count", count)

    cumsum = [0] + np.cumsum(count).tolist()
    c_len = len(cumsum)
    win = min(2 * K + 1, c_len - 1)
    # print(cumsum)
    # print(win)

    print(max([cumsum[i + win] - cumsum[i] for i in range(0, c_len - win, 2)]))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

N, A, B, C = map(int, input().split())

l = []
for i in range(N):
    num = int(input())
    l.append(num)
l = np.array(l)

min_loss = 9999999999999999
for pat in itertools.product(["A", "B", "C", "D"], repeat=N):
    if pat.count("A") > 0 and pat.count("B") > 0 and pat.count("C") > 0:
        pat = np.array(pat)
        pat_A = l[pat == "A"]
        pat_B = l[pat == "B"]
        pat_C = l[pat == "C"]

        loss_A = abs(A-pat_A.sum())+10*(len(pat_A)-1)
        loss_B = abs(B-pat_B.sum())+10*(len(pat_B)-1)
        loss_C = abs(C-pat_C.sum())+10*(len(pat_C)-1)

        loss = loss_A+loss_B+loss_C
        min_loss = min(min_loss, loss)

print(min_loss)


Fixed submission:
N, A, B, C = map(int, input().split())

l_in = []
for i in range(N):
    num = int(input())
    l_in.append(num)


def dfs(cur, a_sum, b_sum, c_sum):
    if cur == N:
        return abs(A-a_sum)+abs(B-b_sum)+abs(C-c_sum)-30 if a_sum*b_sum*c_sum > 0 else 100000000

    pat0 = dfs(cur+1, a_sum, b_sum, c_sum)
    pat1 = dfs(cur+1, a_sum+l_in[cur], b_sum, c_sum)+10
    pat2 = dfs(cur+1, a_sum, b_sum+l_in[cur], c_sum)+10
    pat3 = dfs(cur+1, a_sum, b_sum, c_sum+l_in[cur])+10

    return min(pat0, pat1, pat2, pat3)


print(dfs(0, 0, 0, 0))
Buggy python submission (verdict: Time Limit Exceeded):
A, B, Q = map(int, input().split())
s, t, x = [], [], []
for i in range(A):
    s.append(int(input()))
for i in range(B):
    t.append(int(input()))
for i in range(Q):
    x.append(int(input()))


def find(target, loc):
    if len(target) > 2:
        if loc < target[len(target)//2]:
            return find(target[:len(target)//2+1], loc)
        else:
            return find(target[len(target)//2:], loc)
    elif len(target) == 2:
        if loc <= sum(target)/2:
            return target[0]
        else:
            return target[1]
    else:
        return target[0]


for x_i in x:
    # s -> t
    move_s = 0
    cur = find(s, x_i)
    move_s += abs(cur-x_i)
    end = find(t, cur)
    move_s += abs(end-cur)

    # t -> s
    move_t = 0
    cur = find(t, x_i)
    move_t += abs(cur-x_i)
    end = find(s, cur)
    move_t += abs(end-cur)

    print(min(move_s, move_t))


Fixed submission:
from bisect import bisect_left

A, B, Q = map(int, input().split())
s, t, x = [], [], []
for i in range(A):
    s.append(int(input()))
for i in range(B):
    t.append(int(input()))
for i in range(Q):
    x.append(int(input()))


for x_i in x:
    s_r_index = bisect_left(s, x_i)
    if s_r_index >= len(s):
        s_r = 1e18
    else:
        s_r = s[s_r_index]

    if s_r_index > 0:
        s_l = s[s_r_index-1]
    else:
        s_l = -1e18

    t_r_index = bisect_left(t, x_i)
    if t_r_index >= len(t):
        t_r = 1e18
    else:
        t_r = t[t_r_index]

    if t_r_index > 0:
        t_l = t[t_r_index-1]
    else:
        t_l = -1e18

    move_length = [abs(x_i-s_l)+abs(s_l-t_l),
                   abs(x_i-s_l)+abs(s_l-t_r),
                   abs(x_i-s_r)+abs(s_r-t_l),
                   abs(x_i-s_r)+abs(s_r-t_r),
                   abs(x_i-t_l)+abs(t_l-s_l),
                   abs(x_i-t_l)+abs(t_l-s_r),
                   abs(x_i-t_r)+abs(t_r-s_l),
                   abs(x_i-t_r)+abs(t_r-s_r)]
    print(min(move_length))
Buggy python submission (verdict: Runtime Error):
import numpy as np

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

diff = np.diff(h)
max_list = []
min_list = []

sign = 1
for i, d in enumerate(diff):
    if d > 0 and sign == -1:
        sign = 1
        min_list.append(h[i])

    if d < 0 and sign == 1:
        sign = -1
        max_list.append(h[i])
if diff[-1] > 0:
    max_list.append(h[-1])


def add(val, max_list, min_list):
    if len(max_list) > 1:
        min_val = min(min_list)
        split_index = min_list.index(min_val)+1
        return min_val-val + \
            add(min_val, max_list[:split_index], min_list[:split_index-1]) + \
            add(min_val, max_list[split_index:], min_list[split_index:])
    else:
        return max_list[0]-val


print(add(0, max_list, min_list))


Fixed submission:
import numpy as np

N = int(input())
h = [0]+list(map(int, input().split()))+[0]

diff = np.diff(h).tolist()
max_list = []
min_list = []

sign = 1
for i, d in enumerate(diff):
    if d > 0 and sign < 0:
        sign = d
        min_list.append(h[i])

    if d < 0 and sign > 0:
        sign = d
        max_list.append(h[i])


def add(val, max_list, min_list):
    if len(max_list) > 1:
        min_val = min(min_list)
        split_index = min_list.index(min_val)+1
        return min_val-val + \
            add(min_val, max_list[:split_index], min_list[:split_index-1]) + \
            add(min_val, max_list[split_index:], min_list[split_index:])
    else:
        return max_list[0]-val


if max(h) == 0:
    print(0)
else:
    print(add(0, max_list, min_list))
Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from copy import deepcopy

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

PY = []
for _ in range(M):
    PY.append(list(map(int, input().split())))

sorted_PY = deepcopy(PY)
sorted_PY.sort(key=lambda x: x[1])

p_count_dict = defaultdict(lambda: 0)
y_dict = {}

for py in sorted_PY:
    p_count_dict[py[0]] += 1
    y_dict[py[1]] = p_count_dict[py[0]]

for py in PY:
    print(f'{py[0]:0>6}{y_dict[py[1]]:0>6}')


Fixed submission:
import sys
from collections import defaultdict
from copy import deepcopy

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

PY = []
for _ in range(M):
    PY.append(list(map(int, input().split())))

sorted_PY = deepcopy(PY)
sorted_PY.sort(key=lambda x: x[1])

p_count_dict = defaultdict(lambda: 0)
y_dict = {}

for py in sorted_PY:
    p_count_dict[py[0]] += 1
    y_dict[py[1]] = p_count_dict[py[0]]

for py in PY:
    # print(f'{py[0]:0>6}{y_dict[py[1]]:0>6}')
    print('{}{}'.format(str(py[0]).zfill(6), str(y_dict[py[1]]).zfill(6)))
Buggy python submission (verdict: Runtime Error):
# -*- coding:utf-8 -*-

from collections import defaultdict

N, Q = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
px = [tuple(map(int, input().split())) for _ in range(Q)]

parent_map = {b: a for a, b in ab}
child_map = defaultdict(list)
for parent, child in ab:
    child_map[parent].append(child)

operation_map = defaultdict(int)
for p, x in px:
    operation_map[p] += x

counter = [0] * N


def count(parent_no, parent_counter):
    for child_no in child_map[parent_no]:
        child_count = parent_counter + operation_map[child_no]
        counter[child_no-1] = child_count
        count(child_no, child_count)


counter[0] = operation_map[1]
count(1, counter[0])

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


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

from collections import defaultdict

N, Q = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
px = [tuple(map(int, input().split())) for _ in range(Q)]

parent_map = {b: a for a, b in ab}
child_map = defaultdict(list)
for parent, child in ab:
    child_map[parent].append(child)

operation_map = defaultdict(int)
for p, x in px:
    operation_map[p] += x

counter = [0] * N

counter[0] = operation_map[1]
stack = list(child_map[1])
node_no = 0
while True:
    try:
        node_no = stack.pop()
    except IndexError:
        break

    parent_no = parent_map[node_no]
    counter[node_no - 1] = counter[parent_no - 1] + operation_map[node_no]
    stack += list(child_map[node_no])

print(' '.join(map(str, counter)))
Buggy python submission (verdict: Runtime Error):
# -*- coding:utf-8 -*-

import math

N = int(input())

type_dict = {}
for _ in range(N):
    s = input()
    counts = (
        s.count('a'), s.count('b'), s.count('c'), s.count('d'),
        s.count('e'), s.count('f'), s.count('g'), s.count('h'),
        s.count('i'), s.count('j'), s.count('k'), s.count('l'),
        s.count('m'), s.count('n'), s.count('o'), s.count('p'),
        s.count('q'), s.count('r'), s.count('s'), s.count('t'),
        s.count('u'), s.count('v'), s.count('w'), s.count('x'),
        s.count('y'), s.count('z')
    )
    if counts in type_dict:
        type_dict[counts] = type_dict[counts] + 1
    else:
        type_dict[counts] = 1


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


print(sum([combinations_count(x, 2) for x in type_dict.items() if x > 1]))


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

import math

N = int(input())

type_dict = {}
for _ in range(N):
    s = input()
    counts = (
        s.count('a'), s.count('b'), s.count('c'), s.count('d'),
        s.count('e'), s.count('f'), s.count('g'), s.count('h'),
        s.count('i'), s.count('j'), s.count('k'), s.count('l'),
        s.count('m'), s.count('n'), s.count('o'), s.count('p'),
        s.count('q'), s.count('r'), s.count('s'), s.count('t'),
        s.count('u'), s.count('v'), s.count('w'), s.count('x'),
        s.count('y'), s.count('z')
    )
    if counts in type_dict:
        type_dict[counts] = type_dict[counts] + 1
    else:
        type_dict[counts] = 1


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


print(sum([combinations_count(x, 2) for x in type_dict.values() if x > 1]))