Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter
from math import log,ceil
from fractions import gcd
mod = 10**9 + 7

def lcm(a:int,b:int):
    return a * b // gcd(a, b)

def main():
    N = int(input())
    A  =list(map(int,input().split()))
    neko = 1
    for a in A:
        neko = lcm(neko,a)
    sm = 0
    for a in A:
        sm = (sm + neko // a)%mod
    print(sm)

    return


if __name__ == "__main__":
    main()

Fixed submission:
from operator import itemgetter
from math import log,ceil
from fractions import gcd
mod = 10**9 + 7


def euclid(a:int,b:int)->(int,int):
    #return x,y s.t ax + by = gcd(a,b)
    #a > b >= 0
    if b == 0:
        return 1,0
    x,y = euclid(b,a%b)
    return y,x - y*(a // b)

def inverse(a:int,mod:int)->int:
    #gcd(p,b) == 1
    if mod > a:
        n,x = euclid(mod,a)
    else:
        x,n = euclid(a,mod)
    return x

def devide_mod(a:int,b:int,mod:int)->int:
    #a // b
    x = inverse(b,mod)
    return  (a*x)%mod



def lcm(a:int,b:int):
    return a*b // gcd(a, b)

def main():
    N = int(input())
    A  =list(map(int,input().split()))
    neko = 1
    for a in A:
        neko = lcm(neko,a)
    sm = 0
    neko = neko%mod
    for a in A:
        sm = (sm + devide_mod(neko , a,mod))%mod
    print(sm)

    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):

def main():
    X = int(input())
    A = [False]*(10**5 + 1)
    A[100] = True
    A[101] = True
    A[102] = True
    A[103] = True
    A[104] = True
    A[105] = True
    for i in range(100,X+1):
        if A[i]:
            A[i+100] = True
            A[i+101] = True
            A[i+102] = True
            A[i+103] = True
            A[i+104] = True
            A[i+105] = True
    if A[X]:
        print(1)
    else:
        print(0)
    return 

main()

Fixed submission:

def main():
    X = int(input())
    A = [False]*(110000)
    A[100] = True
    A[101] = True
    A[102] = True
    A[103] = True
    A[104] = True
    A[105] = True
    for i in range(100,X+1):
        if A[i]:
            A[i+100] = True
            A[i+101] = True
            A[i+102] = True
            A[i+103] = True
            A[i+104] = True
            A[i+105] = True
    if A[X]:
        print(1)
    else:
        print(0)
    return 

main()
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))

def main():
    dic = {}
    for i in range(1,N + 1):
        A[ i ] += A[ i - 1 ]
    for j in range(N + 1):
        if (A[j] - j)%K in dic:
            dic[(A[j] - j)%K].append(j)
        else:
            dic[(A[j] - j)%K] = [j]

    ans = 0
    
    for i in range(1,N + 1):
        tmp = dic[(A[i] - i)%K]
        for x in tmp:
            if i - K < x and x < i:
                ans += 1
    print(ans)
    return 

if __name__ == "__main__":
    main()

Fixed submission:
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))


from bisect import bisect_right as br
def main():
    dic = {}
    for i in range(1,N + 1):
        A[ i ] += A[ i - 1 ]
    for j in range(N + 1):
        if (A[j] - j)%K in dic:
            dic[(A[j] - j)%K].append(j)
        else:
            dic[(A[j] - j)%K] = [j]

    ans = 0
    
    for i in range(1,N + 1):
        tmp = dic[(A[i] - i)%K]
        left = br(tmp,i - K)
        right = br(tmp,i) - 1
        ans += right - left
    print(ans)
    return 

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def check(N_:int,S_:list,F_:list,upper:int,K_:int)->bool:
    #A_i > A_j (i < j)
    cnt = 0
    for i in range(N_):
        s = S_[i]
        if s > upper:
            cnt += ceil((s - upper)/F_[i])
            if cnt > K_:
                return False
        else:
            return True
    return True


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    F = list(map(int,input().split()))
    A.sort(reverse = True)
    F.sort()
    S = [f*a for f,a in zip(F,A)]
    right = sum(S)
    left = -1
    while left + 1 < right:
        mid = (right + left) // 2
        if mid == right:
            break
        if check(N,S,F,mid,K):
            right = mid
        else:
            left = mid + 1
    print(mid)
    return

if __name__ == "__main__":
    main()

Fixed submission:
from math import ceil

def check(N_:int,S_:list,F_:list,upper:int,K_:int)->bool:
    #A_i > A_j (i < j)
    cnt = 0
    for i in range(N_):
        s = S_[i]
        if s > upper:
            cnt += ceil((s - upper)/F_[i])
            if cnt > K_:
                return False
    return True


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    F = list(map(int,input().split()))
    A.sort(reverse = True)
    F.sort()
    S = [f*a for f,a in zip(F,A)]
    right = max(S)
    left = -1
    while left + 1 < right:
        mid = (right + left) // 2
        if mid == right:
            break
        if check(N,S,F,mid,K):
            right = mid
        else:
            left = mid
    print(right)
    return

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    dp = [float("inf")]*(2**N)
    S = [sum([2**(c - 1) for c in abc[2:]]) for abc in ABC]
    dp[0] = 0
    for i in range(M):
        for bit in range(2**N):
            result = int(bit | S[i])
            dp[result] = min(dp[result],dp[bit] + ABC[i][0])        
    print(dp[2**N - 1] if dp[2**N - 1] < float("inf") else -1)
    return

if __name__ == "__main__":
    main()

Fixed submission:
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    dp = [float("inf")]*(2**N)
    S = [sum([2**(c - 1) for c in abc[2:]]) for abc in ABC]
    dp[0] = 0
    for i in range(M):
        for bit in range(2**N):
            result = int(bit | S[i])
            dp[result] = min(dp[result],dp[bit] + ABC[i][0])        
    print(dp[2**N - 1] if dp[2**N - 1] < float("inf") else -1)
    return

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
class Heap:
    
    def maintain_heapify(self,A,i):
        l=2*i+1
        r=2*i+2
        if self.name=='max':
            if l<len(A) and A[l]>A[i]:
                largest=l
            else:
                largest=i
            
            if r<len(A) and A[r]>A[largest]:
                largest=r
            
            if largest!=i:
                A[largest],A[i]=A[i],A[largest]
                self.maintain_heapify(A,largest)

        elif self.name=='min':
            if l<len(A) and A[l]<A[i]:
                smallest=l
            else:
                smallest=i
            if r<len(A) and A[r]<A[smallest]:
                smallest=r
            if smallest!=i:
                A[smallest],A[i]=A[i],A[smallest]
                self.maintain_heapify(A,smallest)

    def build_heap(self,A):
        i=len(A)//2
        while i>=0:
            self.maintain_heapify(A,i)
            i-=1

    def __init__(self,A,name='max'):
        self.name=name
        self.build_heap(A)
        self.heap=A

    def insert(self,v):
        self.heap.append(v)
        self.build_heap(self.heap)

    def deleteroot(self):
        root=self.heap[:1]
        tmp=self.heap[1:len(self.heap)-1]
        self.heap=self.heap[len(self.heap)-1:]+tmp
        self.build_heap(self.heap)
        return root[0]

    def get_root(self):
        return self.heap[0]
    def get_sum(self):
      	for i in range(len(self.heap)):
          self.heap[i] = int(self.heap[i])
        return sum(self.heap)


def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    heap = Heap(A)
    tmp = 0
    for cnt in range(M):
        first = heap.deleteroot()
        plus = first / 2
        heap.insert(plus)
    print(heap.get_sum())
    return
main()


Fixed submission:
def minus(a:str):
    return int(a)*-1

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

import heapq as hq

def main():
    hq.heapify(A)
    for _ in range(M):
        target = hq.heappop(A)
        target = -1*((-1*target) // 2)
        hq.heappush(A,target)
    print(sum(A)*-1)
    return 

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import heapq
a = [6, 3, 2, 4, 5]
heapq.heapify(a)    # 破壊的

print a[0]    # => 2
heapq.heappop(a)    # 最小値をヒープから取り出す
print a[0]    # => 3
heapq.heappush(a, 1)    # ヒープに要素を追加する
print a[0]    # => 1

Fixed submission:
def main():
    N  = int(input())
    ans = (N-1)*N // 2
    print(ans)
    return
main()
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
Edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b, = map(int,input().split())
    Edge[a].append(b)
    Edge[b].append(a)

PX = [list(map(int,input().split())) for _ in range(Q)]

visited = [True for _ in range(N+1)]
visited[1] = False
queue = [1]
Ans = [0]*(N+1)

for p,x in PX:
    Ans[p] += x

while len(queue) > 0:
    nextnode = queue.pop(0)
    for e in Edge[nextnode]:
        if visited[e]:
            visited[e] = False
            queue.append(e)
            Ans[e] += Ans[nextnode]
print(*Ans[1:],sep = " ")



Fixed submission:
N,Q = map(int,input().split())
Edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b, = map(int,input().split())
    Edge[a].append(b)
    Edge[b].append(a)

PX = [list(map(int,input().split())) for _ in range(Q)]

visited = [True for _ in range(N+1)]
visited[1] = False
stack = [1]
Ans = [0]*(N+1)

for p,x in PX:
    Ans[p] += x

while len(stack) > 0:
    nextnode = stack.pop()
    for e in Edge[nextnode]:
        if visited[e]:
            visited[e] = False
            stack.append(e)
            Ans[e] += Ans[nextnode]
print(*Ans[1:],sep = " ")

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
Edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b, = map(int,input().split())
    Edge[a].append(b)
    Edge[b].append(a)

PX = [list(map(int,input().split())) for _ in range(Q)]

visited = [True for _ in range(N+1)]
visited[1] = False
queue = [1]
Ans = [0]*(N+1)

for p,x in PX:
    Ans[p] += x

while len(queue) > 0:
    nextnode = queue.pop(0)
    for e in Edge[nextnode]:
        if visited[e]:
            visited[e] = False
            queue.append(e)
            Ans[e] += Ans[nextnode]
print(*Ans[1:],sep = " ")



Fixed submission:
N,Q = map(int,input().split())
Edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b, = map(int,input().split())
    Edge[a].append(b)
    Edge[b].append(a)

PX = [list(map(int,input().split())) for _ in range(Q)]

visited = [True for _ in range(N+1)]
visited[1] = False
stack = [1]
Ans = [0]*(N+1)

for p,x in PX:
    Ans[p] += x

while len(stack) > 0:
    nextnode = stack.pop()
    for e in Edge[nextnode]:
        if visited[e]:
            visited[e] = False
            stack.append(e)
            Ans[e] += Ans[nextnode]
print(*Ans[1:],sep = " ")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
Ans = []
temp = [0]*(N+1)

def factor(num):
    sqrt = num**0.5
    for i in range(1,int(num**0.5)+1):
        if i == sqrt:
            temp[i] += 1
        elif num%i == 0:
            temp[i] += 1
            temp[num//i] += 1
    return


for a,i in zip(A[::-1],range(N-1,-1,-1)):
    if a == 1 and temp[i+1] == 0:
        factor(i+1)
        Ans.append(i+1)
    elif temp[i+1]%2 != a:
        factor(i+1)
        Ans.append(i+1)
if len(Ans) == 0:
    print(0)
else:
    print(len(Ans))
    print(*Ans,sep = " ")

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
Ans = []
temp = [0]*(N+1)

def factor(num):
    sqrt = num**0.5
    for i in range(1,int(num**0.5)+1):
        if i == sqrt:
            temp[i] += 1
        elif num%i == 0:
            temp[i] += 1
            temp[num//i] += 1
    return


for a,i in zip(A[::-1],range(N-1,-1,-1)):
    if a == 1 and temp[i+1] == 0:
        factor(i+1)
        Ans.append(i+1)
    elif temp[i+1]%2 != a:
        factor(i+1)
        Ans.append(i+1)
if len(Ans) == 0:
    print(0)
else:
    print(len(Ans))
    print(*Ans,sep = " ")
Buggy python submission (verdict: Runtime Error):
_N,_K = map(int,input().split())
_mod = 10**9 + 7

def framod(fn, fmod, fa=1):
    for i in range(1,fn+1):
        fa=fa * i % fmod
    return fa

def power(pn, pr, pmod):
    if pr == 0: return 1
    if pr%2 == 0:
        return power(pn*pn % pmod, pr//2, pmod) % pmod
    if pr%2 == 1:
        return pn * power(pn, pr-1, pmod) % pmod

def comb(ccn, cck, ccmod):
    a=framod(ccn, ccmod)
    b=framod(cck, ccmod)
    c=framod(ccn-cck, ccmod)
    return (a * power(b, ccmod-2, ccmod) * power(c, ccmod-2, ccmod)) % ccmod
    


def solve(i):
    n = i
    r = _K - i
    pattern = comb(_N -_K+1,i,_mod)
    if n == 1:
        return pattern
    else:
        ans = comb(K-1,i-1,_mod)
        return ans*pattern%_mod


for i in range(1,_K+1):
    print(solve(i))

Fixed submission:
def euclid(a:int,b:int)->(int,int):
    #return x,y s.t ax + by = gcd(a,b)
    #a > b >= 0
    if b == 0:
        return 1,0
    x,y = euclid(b,a%b)
    return y,x - y*(a // b)

def inverse(a:int,mod:int)->int:
    #gcd(p,b) == 1
    if mod > a:
        n,x = euclid(mod,a)
    else:
        x,n = euclid(a,mod)
    return x

def devide_mod(a:int,b:int,mod:int)->int:
    #a // b
    x = inverse(b,mod)
    return  (a*x)%mod

mod = 10**9 + 7


def com_init(mx:int ,mod:int)->list:
    fac = [1]*mx
    inv = [1]*mx
    finv = [1]*mx
    for i in range(2,mx):
        fac[i] = fac[i - 1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    return fac,finv,inv

fac,finv ,inv = com_init(10**5,10**9 + 7)

def com(n:int, k:int):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
    N, K = map(int,input().split())
    for i in range(1, K + 1 ):
        print(com(N - K + 1,i)*com(K - 1, i - 1)%mod)
    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from math import gcd
a,b,c,d = map(int,input().split())
ans = b - a + 1#ok
a -= 1#ok

g = gcd(c,d)
temp = c*d/g
cc = -int(a/c) + int(b/c)
dd = -int(a/d) + int(b/d)
cd = -int(a/temp) + int(b / temp)

if c == 1 or d == 1:
    print(0)
else:
    print(ans - cc - dd + cd)

Fixed submission:
from fractions import gcd
a,b,c,d = map(int,input().split())
ans = b - a + 1#ok
a -= 1#ok

g = gcd(c,d)
temp = c*d//g

cc = -int(a//c) + int(b//c)
dd = -int(a//d) + int(b//d)
cd = -int(a//temp) + int(b // temp)

print(ans - cc - dd + cd)

Buggy python submission (verdict: Runtime Error):
from math import gcd
a,b,c,d = map(int,input().split())
ans = b - a + 1#ok
a -= 1#ok

g = gcd(c,d)
n = c / g
m = d / g
temp = n*m*g

ans -= -int(a/c) + int(b/c)
ans -= -int(a/d) + int(b/d)
ans += -int(a/temp) + int(b / temp)

print(int(ans))

Fixed submission:
from fractions import gcd
a,b,c,d = map(int,input().split())
ans = b - a + 1#ok
a -= 1#ok

g = gcd(c,d)
temp = c*d//g

cc = -int(a//c) + int(b//c)
dd = -int(a//d) + int(b//d)
cd = -int(a//temp) + int(b // temp)

print(ans - cc - dd + cd)
Buggy python submission (verdict: Runtime Error):
W,H,x,y = map(int,input().split())
temp1 = [(W-x)*H,x*H]
temp2 = [W*y,W*(H-y)]

ans = max(min(temp1),min(temp2))
if  (W/2 == x and H/2 == y):
    print(W*H/2,1)
elif H/W == y/x:
    print(W*H/2,0)
elif x == 0 or x == W or y == 0 or y == H:
    print(W*H/2,0)
elif min(temp1) == min(temp2):
    print(ans,1)
else:
    print(ans,0)


Fixed submission:
w,h,x,y = map(int,input().split())
if w/2 == x and h/2 == y:
  print(w*h/2,1)
else:
  print(w*h/2,0)
Buggy python submission (verdict: Runtime Error):
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]

cost = N
from operator import itemgetter
XY.sort(key = itemgetter(0))
dic = {}

for i in range(N-1):
    xx,yy = XY[i]
    x,y = XY[i+1]
    temp = (x-xx,y-yy)
    if temp in dic:
        dic[temp] += 1
    else:
        dic[temp] = 1

print(cost - max(dic.values()))


Fixed submission:
N = int(input())
XY = {}
for i in range(N):
    x,y = map(int,input().split())
    XY[(x,y)] = 1
dis = {}

ans = N

for x,y in XY.keys():
    for xx,yy in XY.keys():
        if x != xx or y != yy:
            temp = (xx-x,yy-y)
            if not(temp in dis):
                dis[temp] = 1

for p,q in dis:
    test = 0
    copy = XY.copy()
    for x,y in copy:
            if (x+p,y+q) in copy.keys():
                test += 1
    if N - test < ans:
        ans = N - test
print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
    H,W = map(int,input().split())
    S = [[1 if s == "." else 0 for s in input()] for _ in range(H)]
    R = [[0]*W for _ in range(H)]
    L = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]
    U = [[0]*W for _ in range(H)]

    for h in range(H):
        for w in range(1,W - 1):
            if S[h][w] and S[h][w - 1]:
                L[h][w] += L[h][w - 1] + 1
            if S[h][W - w] and S[h][W - w - 1]:
                R[h][W - w - 1] += R[h][W - w] + 1
        if S[h][W -1] and S[h][W - 2]:
            L[h][W - 1] += L[h][W - 2] + 1
        if S[h][0] and S[h][1]:
            R[h][0] += R[h][1] + 1
    for w in range(W):
        for h in range(1,H-1):
            if S[h-1][w] and S[h][w]:
                U[h][w] += U[h-1][w] + 1
            if S[H - h][w] and S[H - h - 1][w]:
                D[H - h - 1][w] += D[H - h][w] + 1
        if S[H - 1][w] and S[H - 2][w]:
            D[H - 1][w] += D[H-2][w] + 1
        if S[0][w] and S[1][w]:
            U[0][w] += U[1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,U[h][w] + D[h][w] + R[h][w] + L[h][w])
    print(ans + 1)
    return 

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    H,W = map(int,input().split())
    S = [[1 if s == "." else 0 for s in input()] for _ in range(H)]

    if H == 1:
        for w in range(1,W):
            if S[0][w] and S[0][w - 1]:
                S[0][w] += S[0][w - 1]
        print(max(S[0]))
        return
    if W == 1:
        ans = 0
        for h in range(1,H):
            if S[h][0] and S[h-1][0]:
                S[h][0] += S[h - 1][0]
                ans = max(ans,S[h][0])
        print(ans)
        return


    R = [[0]*W for _ in range(H)]
    L = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]
    U = [[0]*W for _ in range(H)]

    for h in range(H):
        for w in range(1,W - 1):
            if S[h][w] and S[h][w - 1]:
                L[h][w] += L[h][w - 1] + 1
            if S[h][W - w] and S[h][W - w - 1]:
                R[h][W - w - 1] += R[h][W - w] + 1
        if S[h][W -1] and S[h][W - 2]:
            L[h][W - 1] += L[h][W - 2] + 1
        if S[h][0] and S[h][1]:
            R[h][0] += R[h][1] + 1
    for w in range(W):
        for h in range(1,H-1):
            if S[h-1][w] and S[h][w]:
                U[h][w] += U[h-1][w] + 1
            if S[H - h][w] and S[H - h - 1][w]:
                D[H - h - 1][w] += D[H - h][w] + 1
        if S[H - 1][w] and S[H - 2][w]:
            D[H - 1][w] += D[H-2][w] + 1
        if S[0][w] and S[1][w]:
            U[0][w] += U[1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,U[h][w] + D[h][w] + R[h][w] + L[h][w])
    print(ans + 1)
    return 

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n = int(input())
UVW = []
UF = [[0,0] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    UF[v][0] = u
    UF[v][1] = w

def search(UF,loc):
    if UF[loc][0] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
print(0)
for i in range(2,n+1):
    if search(UF,2)[1]%2 == 1:
        print(1)
    else:
        print(0)

Fixed submission:
from math import ceil,log2

def main():
    N = int(input())
    UVW = [list(map(int,input().split())) for _ in range(N - 1)]
    edge = [[] for _ in range(N + 1)]
    dis = {}
    for u,v,w in UVW:
        edge[u].append(v)
        edge[v].append(u)
        dis[(u,v)] = w
        dis[(v,u)] = w
    cnt = 0
    queue = [1]
    gone = {1:0}
    while cnt < N:
        node = queue[cnt]
        for e in edge[node]:
            if e not in gone:
                if dis[(node,e)]%2 == 1:
                    gone[e] = (gone[node] + 1)%2
                else:
                    gone[e] = gone[node]
                queue.append(e)
        cnt += 1
    for i in range(1,N + 1):
        print(gone[i])
    return
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
n = int(input())
edge = [[] for _ in range(n+1)]
node = [0]*(n+1)
distance = {}
for _ in range(n-1):
    u,v,w = map(int,input().split())
    edge[u].append(v)
    distance[str(u)+"&"+str(v)] = w

stack = edge[1]
now = 1
while True:
    if len(stack) == 0:
        break
    temp = stack[-1]
    stack.pop(-1)
    for e in edge[temp]:
        stack.append(e)
    if distance[str(now)+"&"+str(temp)]%2 == 1:
        node[temp] = 1
    now = temp
print(*node[1:],sep ="\n")

Fixed submission:
from math import ceil,log2

def main():
    N = int(input())
    UVW = [list(map(int,input().split())) for _ in range(N - 1)]
    edge = [[] for _ in range(N + 1)]
    dis = {}
    for u,v,w in UVW:
        edge[u].append(v)
        edge[v].append(u)
        dis[(u,v)] = w
        dis[(v,u)] = w
    cnt = 0
    queue = [1]
    gone = {1:0}
    while cnt < N:
        node = queue[cnt]
        for e in edge[node]:
            if e not in gone:
                if dis[(node,e)]%2 == 1:
                    gone[e] = (gone[node] + 1)%2
                else:
                    gone[e] = gone[node]
                queue.append(e)
        cnt += 1
    for i in range(1,N + 1):
        print(gone[i])
    return
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from fraction import gcd
n = int(input())
A = list(map(int,input().split()))
left = [0]*(n+1)
right = [0]*(n+2)
for a,aa,i in zip(A,A[::-1],range(1,n+1)):
    left[i] = gcd(a,left[i-1])
    right[n+1-i] = gcd(aa,right[n-i+2])
ans = 1
for i in range(1,n+1):
    if i ==1:
        if ans < right[i+1]:
            ans = right[i+1]
    elif i == n:
        if ans < left[i-1]:
            ans = left[i-1]
    else:
        if ans < gcd(left[i-1],right[i+1]):
            ans = gcd(left[i-1],right[i+1])

print(ans)
    

Fixed submission:
n = int(input())
A = list(map(int,input().split()))
A.sort()
def find(inte):
    re = []
    for i in range(1,int(inte**0.5)+1):
        if inte%i==0:
            re.append(i)
            if i != inte/i:
                re.append(int(inte/i))
    return set(re)
if n==2:
    print(A[1])
else:
    a1 = find(A[0])
    a2 = find(A[1])
    a3 = find(A[2])
    t1 = a1 & a2
    t2 = a2 & a3
    t3 = a1 & a3
    cond = t1 | t2 |t3
    maxi = 0
    for con in cond:
        count = 0
        flag = True
        for a in A:
            if a%con != 0:
                count +=1
            if count >= 2:
                
                flag = False
                break
        if flag and maxi < con:
            maxi = con
    print(maxi)
Buggy python submission (verdict: Time Limit Exceeded):
n,q =map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(q)]
flag = True
Ans = [0]*q
count = -1

for l,r in LR:
    count += 1
    temp = ""
    for s in S[l-1:r]:
        if temp =="A" and s =="C":
            Ans[count] += 1
        temp = s
print(*Ans,sep = "\n")

Fixed submission:
n,q =map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(q)]
temp = ""
S2 = []

for s,i in zip(S,range(n)):
    if temp == "A" and s == "C":
        S2.append(i)
    temp = s

import bisect as bi

for l,r in LR:
    ans = - bi.bisect_right(S2,l-1) + bi.bisect_right(S2,r-1)
    print(ans)