Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
X,Y=map(int,input().split())
import math
def f2(r):

    return inv_t
def co(n,r):
    P = 10**9 + 7
    N = r+1
    inv_t = [0]+[1]
    for i in range(2,N+1):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    ans =1
    for i in range(1,r+1):
        ans = (ans * (n+i-1)) % P
    for i in range(1,r+1):
        ans = (ans * inv_t[i]) % P
    return ans
if (X+Y)%3==0:
    Z=X+Y
    if min(X,Y)-Z//3 >-1:
        #print(1)
        comb = Combination(Z)
        print(comb(Z//3,min(X,Y)-Z//3))
        #print(co(Z//3,min(X,Y)-Z//3))
    else:
        print(0)
else:
    print(0)

Fixed submission:
X,Y=map(int,input().split())
import math

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

def f2(r):

    return inv_t
def co(n,r):
    P = 10**9 + 7
    N = r+1
    inv_t = [0]+[1]
    for i in range(2,N+1):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    ans =1
    for i in range(1,r+1):
        ans = (ans * (n+i-1)) % P
    for i in range(1,r+1):
        ans = (ans * inv_t[i]) % P
    return ans
if (X+Y)%3==0:
    Z=X+Y
    if min(X,Y)-Z//3 >-1:
        #print(1)
        print(combination(Z//3,min(X,Y)-Z//3))
        #print(co(Z//3,min(X,Y)-Z//3))
    else:
        print(0)
else:
    print(0)

Buggy python submission (verdict: Runtime Error):
X,Y=map(int,input().split())
import math
def f2(r):

    return inv_t
def co(n,r):
    P = 10**9 + 7
    N = r+1
    inv_t = [0]+[1]
    for i in range(2,N+1):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    ans =1
    for i in range(1,r+1):
        ans = (ans * (n+i-1)) % P
    for i in range(1,r+1):
        ans = (ans * inv_t[i]) % P
    return ans
if (X+Y)%3==0:
    Z=X+Y
    if min(X,Y)-Z//3 >-1:
        #print(1)
        comb = Combination(Z//3)
        print(comb(Z//3,min(X,Y)-Z//3))
        #print(co(Z//3,min(X,Y)-Z//3))
    else:
        print(0)
else:
    print(0)

Fixed submission:
X,Y=map(int,input().split())
import math

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

def f2(r):

    return inv_t
def co(n,r):
    P = 10**9 + 7
    N = r+1
    inv_t = [0]+[1]
    for i in range(2,N+1):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    ans =1
    for i in range(1,r+1):
        ans = (ans * (n+i-1)) % P
    for i in range(1,r+1):
        ans = (ans * inv_t[i]) % P
    return ans
if (X+Y)%3==0:
    Z=X+Y
    if min(X,Y)-Z//3 >-1:
        #print(1)
        print(combination(Z//3,min(X,Y)-Z//3))
        #print(co(Z//3,min(X,Y)-Z//3))
    else:
        print(0)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np
N,K=map(int,input().split())
A=np.array([int(i) for i in input().split()])
F=np.array([int(i) for i in input().split()])
A=np.sort(A)
F=np.sort(F)[::-1]

Asum=A.sum()
i=0
while True:
    i += 1
    if Asum - np.minimum(A,i//F).sum() <=K:
        print(i)
        sys.exit()

Fixed submission:
import sys
import numpy as np
N,K=map(int,input().split())
A=np.array([int(i) for i in input().split()])
F=np.array([int(i) for i in input().split()])
A=np.sort(A)
F=np.sort(F)[::-1]
 
Asum = A.sum()
def test(x):
    return Asum - np.minimum(A,x//F).sum() <= K
 
l=0
r=10**18*2+1
while r-l > 1:
    #print(l,r)
    m = (l+r)//2
    if test(m):
        r=m
    else:
        l=m
if test(l):
    print(l)
else:
    print(l+1)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
import bisect
N,K = map(int,input().split())
A=np.array([int(i) for i in input().split()])
F=np.array([int(i) for i in input().split()])
A=np.sort(A)
F=np.sort(F)[::-1]
#print(A)
#print(F)
B = A*F
#print(B)
x=np.argsort(B)
B=B[x]
F=F[x]
#print()
#print(F)
#print(B)
for j in range(K):
    index = bisect.bisect_left(B,B[-1]-F[-1])
    B = np.insert(B, index, B[-1]-F[-1])
    F = np.insert(F, index, F[-1])
    B = np.delete(B,-1)
    F = np.delete(F,-1)
    if B[-1] == 0:
        print(0)
        sys.exit()
print(B[-1])

Fixed submission:
import sys
import numpy as np
N,K=map(int,input().split())
A=np.array([int(i) for i in input().split()])
F=np.array([int(i) for i in input().split()])
A=np.sort(A)
F=np.sort(F)[::-1]
 
Asum = A.sum()
def test(x):
    return Asum - np.minimum(A,x//F).sum() <= K
 
l=0
r=10**18*2+1
while r-l > 1:
    #print(l,r)
    m = (l+r)//2
    if test(m):
        r=m
    else:
        l=m
if test(l):
    print(l)
else:
    print(l+1)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N,K = map(int,input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()
F.reverse()
#print(A)
#print(F)
B = np.array(A)*np.array(F)
#print(B)
for j in range(K):
    max_i = np.argmax(B)
    B[max_i] -= F[max_i]
#print(B)
print(max(B))

Fixed submission:
import sys
import numpy as np
N,K=map(int,input().split())
A=np.array([int(i) for i in input().split()])
F=np.array([int(i) for i in input().split()])
A=np.sort(A)
F=np.sort(F)[::-1]
 
Asum = A.sum()
def test(x):
    return Asum - np.minimum(A,x//F).sum() <= K
 
l=0
r=10**18*2+1
while r-l > 1:
    #print(l,r)
    m = (l+r)//2
    if test(m):
        r=m
    else:
        l=m
if test(l):
    print(l)
else:
    print(l+1)
Buggy python submission (verdict: Runtime Error):
A = list(map(int, input().split())) 
return max(0,A[0]-2*A[1])

Fixed submission:
A = list(map(int, input().split())) 
print(max(0,A[0]-2*A[1]))
Buggy python submission (verdict: Runtime Error):
N=int(input())
A = sorted([int(x) for x in input().split()])
B = sorted([int(x) for x in input().split()])
C = sorted([int(x) for x in input().split()])

happy=0
for i in range(0,N-1):
  happy+=B[A[i]]
  if A[i+1] == A[i] + 1:
    happy+=C[A[i]]
happy+=B[A[N-1]]
print(happy)

Fixed submission:
N=int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
happy=0
for i in range(0,N-1):
  happy+=B[A[i]-1]
  if A[i+1] == A[i] + 1:
    happy+=C[A[i]-1]
happy+=B[A[N-1]-1]
print(happy)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

if (A-1) % (B-1) ==0:
	print(int((B-1)/(A-1)))
else:
	print(int((B-1)/(A-1))+1)

Fixed submission:
import sys
A, B = map(int, input().split())

if B == 1:
	print(0)
	sys.exit()

if (B-1) % (A-1) ==0:
	print(int((B-1)/(A-1)))
else:
	print(int((B-1)/(A-1))+1)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
ctr = Counter()
answer = 0
for s in S:
    a = ''.join(sorted(list(s)))
    print(a)
    if a in ctr:
        ans += ctr[a]
    ctr[a] += 1
print(answer)

Fixed submission:
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
ctr = Counter()
answer = 0
for s in S:
    a = ''.join(sorted(list(s)))
    #print(a)
    if a in ctr:
        answer += ctr[a]
    ctr[a] += 1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import collections
N=int(input())
s=['']*N
for i in range(N):
    s[i]=input()
c=list(map(collections.Counter,s))
count=0
for i in range(N):
    count += c[i+1:].count(c[i])
print(count)

Fixed submission:
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
ctr = Counter()
answer = 0
for s in S:
    a = ''.join(sorted(list(s)))
    #print(a)
    if a in ctr:
        answer += ctr[a]
    ctr[a] += 1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S = []
A = []
from collections import Counter
import string
for _ in range(N):
    S.append(input())
L=[]
sum_=[0]*N
for (j,s) in enumerate(S):
  for (i,letter) in enumerate(string.ascii_lowercase):
  	sum_[j] += 2**i*Counter(s)[letter]
  
ANS=Counter(sum_)
ans=0
for i in ANS.values():
  ans += int(i*(i-1)/2)
print(ans)

Fixed submission:
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
ctr = Counter()
answer = 0
for s in S:
    a = ''.join(sorted(list(s)))
    #print(a)
    if a in ctr:
        answer += ctr[a]
    ctr[a] += 1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S = []
A = []
from collections import Counter

for _ in range(N):
    S.append(input())
L=[]
for s in S:
  L.append(Counter(s))

x=0
for i in range(N):
  for j in range(i+1,N):
    if L[i]==L[j]:
    	x+=1
print(x)

Fixed submission:
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
ctr = Counter()
answer = 0
for s in S:
    a = ''.join(sorted(list(s)))
    #print(a)
    if a in ctr:
        answer += ctr[a]
    ctr[a] += 1
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import random
N = int(input())
H = [int(x) for x in input().split()]

if N==1:
    print("Yes")
    sys.exit()

K_left=H[1]-H[0]
if K_left<-1:
    print("No")
    sys.exit()
elif K_left == -1 :
    L_left='-'
elif K_left == 0 :
    L_left='0'
else:
    L_left='+'

for i in range(1,N-1):
    K_right=H[i+1]-H[i]    
    if K_right < -1:
        print("No")
        sys.exit()
    elif K_right == -1 :
        L_right='-'
    elif K_right == 0 :
        L_right='0'
    else:
        L_right='+'

    if L_left =='-' and L_right=='-':
        print("No")
        sys.exit()
    if L_left =='0' and L_right=='-':
        if max(H[0:i]) <= H[i]:
            L_left=L_right
            K_left=K_right
        else:
            print("No")
            sys.exit()
    else:
        L_left=L_right
        K_left=K_right
print("Yes")

Fixed submission:
import sys
import random
N = int(input())
H = [int(x) for x in input().split()]

if N==1:
    print("Yes")
    sys.exit()

K_left=H[1]-H[0]
if K_left<-1:
    print("No")
    sys.exit()
elif K_left == -1 :
    L_left='-'
elif K_left == 0 :
    L_left='0'
else:
    L_left='+'
maxH=max(H[1],H[0])
for i in range(1,N-1):
    K_right = H[i+1]-H[i]    
    if K_right < -1:
        print("No")
        sys.exit()
    elif K_right == -1 :
        L_right='-'
    elif K_right == 0 :
        L_right='0'
    else:
        L_right='+'

    if L_left =='-' and L_right=='-':
        print("No")
        sys.exit()
    if L_left =='0' and L_right=='-':
        if maxH <= H[i]:
            L_left=L_right
            K_left=K_right
        else:
            print("No")
            sys.exit()
    else:
        L_left=L_right
        K_left=K_right
        maxH=max(H[i+1],maxH)
print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
lim=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s))]
if s[0] =="?":
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,len(s)):
    for j in range(13):
        if s[i] ==  "?":
            for k in range(10):
                dp[i][(j*10 + k)%13] += dp[i-1][j]
        else:
            dp[i][(j*10 + int(s[i]))%13] += dp[i-1][j]
print(dp[-1][5]%lim)

Fixed submission:
s=input()
lim=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s))]
if s[0] =="?":
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,len(s)):
    for j in range(13):
        if s[i] ==  "?":
            for k in range(10):
                dp[i][(j*10 + k)%13] = (dp[i][(j*10 + k)%13]+dp[i-1][j])%lim
        else:
            dp[i][(j*10 + int(s[i]))%13] = (dp[i][(j*10 + int(s[i]))%13]+dp[i-1][j])%lim
print(dp[-1][5])
Buggy python submission (verdict: Runtime Error):
import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
B=np.zeros(N)
for a in range(1,N+1)[::-1]:
    if N % a ==0:
        idx=np.arange(a,N+a,a)-1
    else:
        idx=np.arange(a,N,a)-1
    B[a-1] = (A[a-1] - B[idx].sum()) % 2
B=B 
ans=np.where(B!=0)[0]+1
print(len(ans))
if len(ans)!=0:
    print(*ans)

Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
B=[0 for _ in range(N)]
def f(a,N):
    l=[]
    m=2*a
    while m<=N:
        l.append(m)
        m+=a
    return l

for a in range(1,N+1)[::-1]:
    idx=f(a,N)
    b_sum=0
    for i in idx:
        b_sum += B[i-1]
    B[a-1] = (A[a-1] - b_sum) % 2
ans=[i+1 for i in range(N) if B[i] != 0]
print(len(ans))
if len(ans)!=0:
    print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
B=np.zeros(N)
for a in range(1,N+1)[::-1]:
    if N % a ==0:
        idx=np.arange(a,N+a,a)-1
    else:
        idx=np.arange(a,N,a)-1
    B[a-1] = (A[a-1] - B[idx].sum()) % 2
B=B 
ans=np.where(B!=0)[0]+1
print(len(ans))
if len(ans)!=0:
    print(*ans)

Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
B=[0 for _ in range(N)]
def f(a,N):
    l=[]
    m=2*a
    while m<=N:
        l.append(m)
        m+=a
    return l

for a in range(1,N+1)[::-1]:
    idx=f(a,N)
    b_sum=0
    for i in idx:
        b_sum += B[i-1]
    B[a-1] = (A[a-1] - b_sum) % 2
ans=[i+1 for i in range(N) if B[i] != 0]
print(len(ans))
if len(ans)!=0:
    print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
B=np.zeros(N)
for a in range(1,N+1)[::-1]:
    if N % a ==0:
        idx=np.arange(a,N+a,a)-1
    else:
        idx=np.arange(a,N,a)-1
    #print(a,A[a-1],idx,B[idx].sum())
    B[a-1] = (A[a-1] - B[idx].sum())
B=B.astype('int') % 2
ans=np.where(B!=0)[0]+1
print(len(ans))
if len(ans)!=0:
    print(*ans)

Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
B=[0 for _ in range(N)]
def f(a,N):
    l=[]
    m=2*a
    while m<=N:
        l.append(m)
        m+=a
    return l

for a in range(1,N+1)[::-1]:
    idx=f(a,N)
    b_sum=0
    for i in idx:
        b_sum += B[i-1]
    B[a-1] = (A[a-1] - b_sum) % 2
ans=[i+1 for i in range(N) if B[i] != 0]
print(len(ans))
if len(ans)!=0:
    print(*ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
H=10 ** 9 + 7
ans=N-K+1
print(ans)
for i in range(1,K):
    P=(N-K-i+1)/(i+1)
    Q=(K-i)/i
    if ans< H :
        ans=int(ans*P*Q)
        print(ans)
    else:
        ans=int(ans*P*Q % H)
        print(ans)

Fixed submission:
S=input()
if len(set(S)) == 2 and S.count(S[0]) ==2:
    print("Yes")     
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
n=input()
P= list(map(int,input().split()))
x=0
for i in range(0,n-2):
    if P[i+1] != max(P[i],P[i+1],P[i+2]) and P[i+1] != min(P[i],P[i+1],P[i+2]):
        x += 1
        
print(x)

Fixed submission:
n=int(input())
P=list(map(int,input().split()))
x=0
for i in range(0,n-2):
    if P[i+1] != max(P[i],P[i+1],P[i+2]) and P[i+1] != min(P[i],P[i+1],P[i+2]):
        x += 1
        
print(x)
Buggy python submission (verdict: Runtime Error):
N=int(input())
P=list(map(int,input().split()))

D=sorted(D)
K=D[N//2]-D[N//2-1]
print(K)

Fixed submission:
N=int(input())
D=list(map(int,input().split()))
 
D=sorted(D)
K=D[N//2]-D[N//2-1]
print(K)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
import numpy as np
A=np.zeros(N)
B=np.zeros(N)
for i in range(0,N):
  A[i],B[i] = map(int,input().split())

BB=list(set(list(B)))
for b in BB:
  if np.sum(A[B<=b])>b:
    print('No')
    break
else:
  print('Yes')

Fixed submission:
import sys
import bisect
import numpy as np
input = sys.stdin.readline
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i],B[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(A),np.array(B)))
matrix = matrix[:, np.argsort(matrix[1])]
time=0
capacity=0
for a,b in zip(matrix[0],matrix[1]):
    capacity += (b-time) - a
    time = b
    if capacity <0:
        print('No')
        sys.exit()
    #print(capacity,a,b)
print('Yes')

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
import numpy as np
A=np.zeros(N)
B=np.zeros(N)
for i in range(0,N):
  A[i],B[i] = map(int,input().split())

for b in B:
  if np.sum(A[B<=b])>b:
    print('No')
    break
else:
  print('Yes')

Fixed submission:
import sys
import bisect
import numpy as np
input = sys.stdin.readline
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i],B[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(A),np.array(B)))
matrix = matrix[:, np.argsort(matrix[1])]
time=0
capacity=0
for a,b in zip(matrix[0],matrix[1]):
    capacity += (b-time) - a
    time = b
    if capacity <0:
        print('No')
        sys.exit()
    #print(capacity,a,b)
print('Yes')

Buggy python submission (verdict: Runtime Error):
N=int(input())
import numpy as np
A=np.zeros(N)
B=np.zeros(N)
for i in range(0,N):
  A[i],B[i] = map(int,input().split())
  
W=np.zeros((N,np.max(B)))
for i in range(0,N):
  for j in range(int(B[i]-A[i]),int(B[i])):
    W[i][j]=1
    
for b in B:
  if np.sum(W[:,0:b]) > b:
    print('No')
    break
else:
  print('Yes')

    

Fixed submission:
import sys
import bisect
import numpy as np
input = sys.stdin.readline
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i],B[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(A),np.array(B)))
matrix = matrix[:, np.argsort(matrix[1])]
time=0
capacity=0
for a,b in zip(matrix[0],matrix[1]):
    capacity += (b-time) - a
    time = b
    if capacity <0:
        print('No')
        sys.exit()
    #print(capacity,a,b)
print('Yes')
Buggy python submission (verdict: Runtime Error):
import itertools
import collections
N=int(input())
X=[0]*N
Y=[0]*N
for i in range(N):
    X[i],Y[i]=[int(x) for x in input().split()]
p=[]
for c in list(itertools.permutations(zip(X,Y), 2)):
    p.append(str(c[1][0]-c[0][0]) + ',' +str(c[1][1]-c[0][1]))
    #print(c,c[1][0]-c[0][0],c[1][1]-c[0][1])
#print(p)
print(N - collections.Counter(p).most_common()[0][1])

Fixed submission:
import itertools
import collections
import sys
N=int(input())
if N==1:
    print(1)
    sys.exit()
X=[0]*N
Y=[0]*N
for i in range(N):
    X[i],Y[i]=[int(x) for x in input().split()]
p=[]
for c in list(itertools.permutations(zip(X,Y), 2)):
    p.append(str(c[1][0]-c[0][0]) + ',' +str(c[1][1]-c[0][1]))
    #print(c,c[1][0]-c[0][0],c[1][1]-c[0][1])
#print(p)
print(N - collections.Counter(p).most_common()[0][1])

Buggy python submission (verdict: Runtime Error):
import itertools
import collections
N=int(input())
X=[0]*N
Y=[0]*N
for i in range(N):
    X[i],Y[i]=[int(x) for x in input().split()]
p=[]
for c in list(itertools.permutations(zip(X,Y), 2)):
    p.append(str(c[1][0]-c[0][0]) + ',' +str(c[1][1]-c[0][1]))
    #print(c,c[1][0]-c[0][0],c[1][1]-c[0][1])
#print(p)
print(N - collections.Counter(p).most_common()[0][1])

Fixed submission:
import itertools
import collections
import sys
N=int(input())
if N==1:
    print(1)
    sys.exit()
X=[0]*N
Y=[0]*N
for i in range(N):
    X[i],Y[i]=[int(x) for x in input().split()]
p=[]
for c in list(itertools.permutations(zip(X,Y), 2)):
    p.append(str(c[1][0]-c[0][0]) + ',' +str(c[1][1]-c[0][1]))
    #print(c,c[1][0]-c[0][0],c[1][1]-c[0][1])
#print(p)
print(N - collections.Counter(p).most_common()[0][1])
Buggy python submission (verdict: Time Limit Exceeded):
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import time
time.sleep(2)
P,Q,R = map(int,input().split())
print(min(P+Q,min(Q+R,R+P)))

Fixed submission:
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python

P,Q,R = map(int,input().split())
print(min(P+Q,min(Q+R,R+P)))
Buggy python submission (verdict: Runtime Error):
N=int(input())
edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w=[int(x) for x in input().split()]
    if w&1:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
    else:
        edge[u].append((v,1))
        edge[v].append((u,1))
    
color = [None]*(N+1)

def set_color(v,c):
    color[v]=c
    for x,sgn in edge[v]:
        if color[x] is None:
            set_color(x,sgn*c)
set_color(1,1)

for x in color[1:]:
    print((x+1)//2)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

N=int(input())
edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w=[int(x) for x in input().split()]
    if w&1:
        edge[u].append((v,-1))
        edge[v].append((u,-1))
    else:
        edge[u].append((v,1))
        edge[v].append((u,1))
    
color = [None]*(N+1)

def set_color(v,c):
    color[v]=c
    for x,sgn in edge[v]:
        if color[x] is None:
            set_color(x,sgn*c)
set_color(1,1)

for x in color[1:]:
    print((x+1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
count = [1 if S[i:i+2] =='AC' else 0 for i in range(0,N-1)]
for i in range(0,Q):
  l,r=map(int,input().split())
  print(sum(count[l-1:r-1]))

Fixed submission:
N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])

Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()
count = [1 for i in range(0,N) if S[i:i+1] =='AC' else 0]
for i in range(0,Q):
  l,r=map(int,input().split())
  print(sum(count[l-1:r-1]))


Fixed submission:
N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
for i in range(0,Q):
  l,r=map(int,input().split())
  print(S[l-1:r].count('AC'))
  

Fixed submission:
N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])

Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
  l[i],r[i]=map(int,input().split())
  print(S[l-1:r].count('AC'))
  

Fixed submission:
N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
Buggy python submission (verdict: Runtime Error):
import sys
N,M=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(0,N):
  A[i],B[i]=map(int,input().split())
index=sorted(range(len(A)), key=lambda k: A[k])

cost=0
get=0
for i in index:
  if get+B[i]<=M:
    get += B[i]
    cost += A[i]*B[i]
  else:
    cost += A[i]*(M-get)
    print(cost)
	sys.exit()

Fixed submission:
import sys
N,M=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(0,N):
  A[i],B[i]=map(int,input().split())
index=sorted(range(len(A)), key=lambda k: A[k])
cost=0
get=0
for i in index:
  if get+B[i]<M:
    get += B[i]
    cost += A[i]*B[i]
  else:
    cost += A[i]*(M-get)
    print(cost)
    sys.exit()