Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from heapq import heappush,heappop

N = int(input())
array = list(map(int,input().split()))
nega = []
posi = []

for num in array:
  if num >= 0:
    heappush(posi,num)
  else:
    heappush(nega,num)

nega = [num*(-1) for num in nega]

if len(nega)%2==0:
  ans = sum(nega) + sum(posi)
else:
  min_posi = heappop(posi)
  max_nega = heappop(nega)
  if min_posi > max_nega:
    ans = sum(nega) + sum(posi) + min_posi - max_nega
  else:
    ans = sum(nega) + sum(posi) - min_posi + max_nega
    
print(ans)

Fixed submission:
from heapq import heappush,heappop

N = int(input())
array = list(map(int,input().split()))
nega = []
posi = []

for num in array:
  if num >= 0:
    heappush(posi,num)
  else:
    heappush(nega,num*(-1))


if len(nega)%2==0:
  ans = sum(nega) + sum(posi)
else:
  if len(nega)==N:
    max_nega = heappop(nega)
    ans = sum(nega) - max_nega
  else:
    min_posi = heappop(posi)
    max_nega = heappop(nega)
    if min_posi > max_nega:
      ans = sum(nega) + sum(posi) + min_posi - max_nega
    else:
      ans = sum(nega) + sum(posi) - min_posi + max_nega

print(ans)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
K = int(input())
 
arr = [e, d, c, b, a]
leng_arr = []
for i in range(len(arr)):
  for j in range(4-i):
    leng = arr[i]-arr[j+1]
    leng_arr.append(leng)
    
if all([i =< k for i in leng_arr]):
  print('Yay')
else:
  print(':(')

Fixed submission:
A = [int(input()) for i in range(5)]
K = int(input())

if (A[-1]-A[0] <= K):
    print("Yay!")
else:
    print(":(")

Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

arr = [e, d, c, b, a]
leng_arr = []
for i in range(len(arr)):
  for j in range(4-i):
    leng = arr[i]-arr[j+1]
    leng_arr.append(leng)
    
if all([i =< k for i in leng_arr]):
  print('Yay')
else:
  print(':(')

Fixed submission:
A = [int(input()) for i in range(5)]
K = int(input())

if (A[-1]-A[0] <= K):
    print("Yay!")
else:
    print(":(")

Buggy python submission (verdict: Runtime Error):
arr = [e, d, c, b, a]
leng_arr = []
for i in range(len(arr)):
  for j in range(4-i):
    leng = arr[i]-arr[j+1]
    leng_arr.append(leng)
    
if all([i =< k for i in leng_arr]):
  print('Yay')
else:
  print(':(')
  

  

Fixed submission:
A = [int(input()) for i in range(5)]
K = int(input())

if (A[-1]-A[0] <= K):
    print("Yay!")
else:
    print(":(")
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int,input().split())
S = input()
for _ in range(Q):
  s,e = map(int,input().split())
  print(S[s-1:e].count('AC'))
  

Fixed submission:
N, Q = map(int,input().split())
S = input()
arr = [0]*N
num = 0
for i in range(N-1):
  if (S[i]=='A')&(S[i+1]=='C'):
    num += 1
  arr[i+1] = num

for _ in range(Q):
  start,end = map(int,input().split())
  print(arr[end-1]-arr[start-1])
Buggy python submission (verdict: Time Limit Exceeded):
a,b = map(int,input().split())
def XOR(start,end):
  xor =  start
  for i in range(a+1,b+1):
    xor = xor^i
    #print(xor)
  print(xor)

if __name__ ==  '__main__':
  XOR(a,b)
    


Fixed submission:
a,b = map(int,input().split())
def XOR(start,end):
  xor =  start
  if end-start < 10:
      for i in range(a+1,b+1):
        xor = xor^i
        #print('end={0},xor={1}'.format(i,xor))
      print(xor)
  else:
    if start%2==0:
      new_start = start-1
    else:
      new_start = start
    
    if (end - new_start)%4==0:
      if start%2==0:
        print(0)
      else:
        print(start)
    elif (end - new_start)%4==1:
      if start%2==0:
        print(end)
      else:
        print(start^end)
    elif (end - new_start)%4==2:
      if start%2==0:
        print((end-1)^end)
      else:
        print(start^(end-1)^end)
    else:
      if start%2==0:
        print((end-2)^(end-1)^end)
      else:
        print(start^(end-2)^(end-1)^end)

if __name__ ==  '__main__':
  XOR(a,b)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = list(map(int, input().split()))
costs = list(map(int, input().split()))

dp = [0]*N

dp[0] = 0

for j in range(1,N,1):
  dev_costs = []
  k = 1
  while j-k >= 0:
    dev_cost = dp[j-k] + abs(costs[j]-costs[j-k])
    dev_costs.append(dev_cost)
    if k ==  K:
      break
    k += 1
    
  dp[j] = min(dev_costs)
    
print(dp[-1])

Fixed submission:
N,K = list(map(int, input().split()))
costs = list(map(int, input().split()))

dp = [0]*N

dp[0] = 0

for j in range(1,N,1):
  dev_costs = []
  k = 1
  while j-k >= 0:
    dev_cost = dp[j-k] + abs(costs[j]-costs[j-k])
    dev_costs.append(dev_cost)
    if k ==  K:
      break
    k += 1
    
  dp[j] = min(dev_costs)
    
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  _w,_v = map(int,input().split())
  for w in range(W+1):
    if w-_w >= 0:
      dp[i+1][w] = max(dp[i][w],dp[i][w-_w]+_v)
    else:
      dp[i+1][w] = dp[i][w]

print(dp[N][W])

Fixed submission:
import numpy as np

N,W = map(int,input().split())
w,v = [0]*N ,[0]*N
arr = [map(int,input().split()) for _ in range(N)]
dp = np.zeros(W+1,dtype= np.int64)

for w,v in arr:
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
H,W,K = map(int, input().split())
# HとWは道の数を決定
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          # 二桁連続で1の場合は処理を省く
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        for l in range(W-1):
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
          else:
            dp[i+1][l] += dp[i][l]
        #print(dp[i+1])

  print(dp[-1][K-1]%(1000000007)

Fixed submission:
H,W,K = map(int, input().split())
# HとWは道の数を決定
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          # 二桁連続で1の場合は処理を省く
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        l = 0
        while l < W:
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
            l += 1
          else:
            dp[i+1][l] += dp[i][l]
          l += 1
        #print('pre',dp[i])
        #print(dp[i+1])

  print(dp[-1][K-1]%(1000000007))
Buggy python submission (verdict: Runtime Error):
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

N,M = map(int,input().split())
arr = [i for i in make_divisors(M) if i>N]
print(M//min(arr))


Fixed submission:
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

N,M = map(int,input().split())
arr = [i for i in make_divisors(M) if i>=N]
print(M//min(arr))
Buggy python submission (verdict: Runtime Error):
def main(a,b):
  if (a*b) % 2 == 0:
    print('Even')
  else:
    print('Odd')

main(a,b)

Fixed submission:
def main(a,b):
  if (a*b) % 2 == 0:
    print('Even')
  else:
    print('Odd')

a,b = map(int, input().split())
main(a,b)
Buggy python submission (verdict: Runtime Error):
a,b,c = int(input())
testList = [a,b,c]

def countOne(self,list):
  count =0
  for i in list:
    if i == 0:
      count +=1
  return count

print(countOne(testList))


Fixed submission:
strTest = input()
print(strTest.count("1"))

Buggy python submission (verdict: Runtime Error):
a,b,c = int(input())
testList = [a,b,c]

def countOne(self,list):
  count =0
  for i in list:
    if i == 0:
      count +=1
  return count

print(countOne(list))


Fixed submission:
strTest = input()
print(strTest.count("1"))

Buggy python submission (verdict: Runtime Error):
list = list(input().split(""))

def countOne(self,list):
  count =0
  for i in list:
    if i == 0:
      count +=1
  return count

print(countOne(list))

Fixed submission:
strTest = input()
print(strTest.count("1"))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]] = max(d[ab[0]],H[ab[1]-1])
    else:
        d[ab[0]] = H[ab[1]-1]
    if ab[1] in d.keys():
        d[ab[1]] = max(d[ab[1]],H[ab[0]-1])
    else:
        d[ab[1]] = H[ab[0]-1]
    s = s | set(ab)

count = 0
for i in d.keys():
    if H[i-1] > d[i]:
        count += 1

count += N - len(s)

print(count)

Fixed submission:
N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = []

for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]] = max(d[ab[0]],H[ab[1]-1])
    else:
        d[ab[0]] = H[ab[1]-1]
    if ab[1] in d.keys():
        d[ab[1]] = max(d[ab[1]],H[ab[0]-1])
    else:
        d[ab[1]] = H[ab[0]-1]
    s.append(ab[0])
    s.append(ab[1])

count = 0
for i in d.keys():
    if H[i-1] > d[i]:
        count += 1

count += N - len(set(s))

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]].append(ab[1])
    else:
        d[ab[0]] = [ab[1]]
    if ab[1] in d.keys():
        d[ab[1]].append(ab[0])
    else:
        d[ab[1]] = [ab[0]]
    s = s | set(ab)

count = 0
for i in d.keys():
    for j in list(set(d[i])):
        if H[i-1] <= H[j-1]:
            break
    else:
        count += 1
count += N - len(s)

print(count)

Fixed submission:
N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = []

for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]] = max(d[ab[0]],H[ab[1]-1])
    else:
        d[ab[0]] = H[ab[1]-1]
    if ab[1] in d.keys():
        d[ab[1]] = max(d[ab[1]],H[ab[0]-1])
    else:
        d[ab[1]] = H[ab[0]-1]
    s.append(ab[0])
    s.append(ab[1])

count = 0
for i in d.keys():
    if H[i-1] > d[i]:
        count += 1

count += N - len(set(s))

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()[::-1]
MOD = 2019

r = 0
C = [0 for _ in range(MOD)]
C[0] = 1

for i,s in enumerate(S):
    r += int(s)*((10**i)%MOD)
    r %= MOD
    C[r] += 1

a = 0
for c in C:
    a += c*(c-1)/2

print(int(a))


Fixed submission:
S = input()[::-1]
MOD = 2019

r = 0
C = [0 for _ in range(MOD)]
C[0] = 1

for i,s in enumerate(S):
    r += int(s)*pow(10,i,MOD)
    r %= MOD
    C[r] += 1

a = 0
for c in C:
    a += c*(c-1)/2

print(int(a))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
p = list(map(int,input().split()))

s = 0
for i in range(N-K+1):
    s_tmp = sum(p[i:i+K])
    if s < s_tmp:
        s = s_tmp

print((s+K)/2)


Fixed submission:
N,K = map(int,input().split())
p = list(map(int,input().split()))

s = s_tmp = sum(p[0:K])
for i in range(N-K):
    s_tmp = s_tmp - p[i] + p[i+K]
    if s < s_tmp:
        s = s_tmp

print((s+K)/2)
Buggy python submission (verdict: Time Limit Exceeded):
A,B = map(int,input().split())

while B:
    A,B = B, A%B
g = A
g_ = g

count = 0
l = []
i = 2
while i <= g_:
    while g%i == 0:
        g = g/i
        l.append(i)
    l = list(set(l))
    i = i+1

print(1+len(l))

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

def gcd(x,y):
    while y:
        x,y = y, x%y
    return x

g = gcd(A,B)

count = 0
l = []

while g%2 == 0:
    l.append(2)
    g //= 2
i = 3
while i**2 <= g:
    if g%i == 0:
        l.append(i)
        g //= i
    else:
        i += 2
if g != 1:
    l.append(g)

print(len(set(l))+1)
Buggy python submission (verdict: Runtime Error):
class Node:
    def __init__(self,data,parent):
        self.data = data
        self.left = None
        self.right = None
        self.parent = parent
        self.same = 1

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self,data):
        n = self.root
        if n == None:
            self.root = Node(data,None)
            return
        else:
            while True:
                if n.data > data:
                    if n.left is None:
                        n.left = Node(data,n)
                        return
                    n = n.left
                elif n.data < data:
                    if n.right is None:
                        n.right = Node(data,n)
                        return
                    n = n.right
                elif n.data == data:
                    n.same += 1
                    return
    
    def delete_max(self):
        n = self.root
        while True:
            if n.right == None:
                break
            else:
                n = n.right
        tmp = n.data//2
        if n.same > 1:
            n.same -= 1
        else:
            if n.left == None:
                n.parent.right = None
            else:
                n.parent.right = n.left
                n.left.parent = n.parent
        self.insert(tmp)
    
    def sum_bst(self,node):
        if node.left == None and node.right == None:
            return node.data*node.same
        else:
            s = node.data*node.same
            if node.left != None:
                s += self.sum_bst(node.left)
            if node.right != None:
                s += self.sum_bst(node.right)
            return s

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

bst = BST()
for a in list(map(int,input().split())):
    bst.insert(a)
for i in range(M):
    bst.delete_max()
print(bst.sum_bst(bst.root))


Fixed submission:
import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = list(map(lambda x:x*(-1), A))

heapq.heapify(A)

for _ in range(M):
    A_max = heapq.heappop(A)*(-1)
    heapq.heappush(A, (A_max//2)*(-1))

print(sum(A)*(-1))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

for i in range(M):
    a = A.pop(-1)//2
    bisect.insort_left(A,a)

print(sum(A))

Fixed submission:
import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = list(map(lambda x:x*(-1), A))

heapq.heapify(A)

for _ in range(M):
    A_max = heapq.heappop(A)*(-1)
    heapq.heappush(A, (A_max//2)*(-1))

print(sum(A)*(-1))
Buggy python submission (verdict: Runtime Error):
N = int(input())
X,Y = [],[]
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
inf = 10**10

d = {}
for i in range(N):
    for j in range(i+1,N):
        if X[i] >= X[j]:
            r,l = i,j
        else:
            r,l = j,i
        k = (X[r]-X[l],Y[r]-Y[l])
        if k in d.keys():
            d[k] += 1
        else:
            d[k] = 1

print(N-(max(d.values())))

Fixed submission:
N = int(input())
X,Y = [],[]
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
inf = 10**10

d = {}
for i in range(N):
    for j in range(i+1,N):
        if X[i] > X[j]:
            r,l = i,j
        elif X[i] == X[j]:
            if Y[i] > Y[j]:
                r,l = i,j
            else:
                r,l = j,i
        else:
            r,l = j,i
        k = (X[r]-X[l],Y[r]-Y[l])
        if k in d.keys():
            d[k] += 1
        else:
            d[k] = 1

if N == 1:
    print(1)
else:
    print(N-(max(d.values())))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

m,p = [],[]
m_total = 0
p_total = 0
p_max,p_min = 0,10**10
c,p_min_idx,p_max_idx = 0,0,0
for a in A:
    if a < 0:
        m_total += a
        m.append(a)
    else:
        if p_min > a:
            p_min = a
            p_min_idx = c
        if p_max < a:
            p_max = a
            p_max_idx = c
        p_total += a
        p.append(a)
        c += 1

if len(m) > 0:
    print(p_total-m_total)
    for i,v in enumerate(p):
        if i != p_max_idx:
            print(m[0], v)
            m[0] -= v
    for i in range(len(m)):
        print(p[p_max_idx],m[i])
        p[p_max_idx] -= m[i]
else:
    print(p_total-2*p_min)
    for i in range(len(p)-1):
        if i != p_min_idx:
            print(p[p_min_idx],p[i])
            p[p_min_idx] -= p[i]
    print(p[-1],p[p_min_idx])

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

p,m = [],[]
p_total = 0
m_total = 0
p_max,p_min = 0,10**10
m_max,m_min = -10**10,0
p_count,p_min_idx,p_max_idx = 0,0,0
m_count,m_min_idx,m_max_idx = 0,0,0
for a in A:
    if a < 0:
        if m_min > a:
            m_min = a
            m_min_idx = m_count
        if m_max < a:
            m_max = a
            m_max_idx = m_count
        m_total += a
        m.append(a)
        m_count += 1
    else:
        if p_min > a:
            p_min = a
            p_min_idx = p_count
        if p_max < a:
            p_max = a
            p_max_idx = p_count
        p_total += a
        p.append(a)
        p_count += 1

if len(m) == 0:
    print(p_total-2*p_min)
    for i in range(len(p)-1):
        if i != p_min_idx:
            print(p[p_min_idx],p[i])
            p[p_min_idx] -= p[i]
    print(p[-1],p[p_min_idx])

elif len(p) == 0:
    print(2*m_max-m_total)
    for i in range(len(m)-1):
        if i != m_max_idx:
            print(m[m_max_idx],m[i])
            m[m_max_idx] -= m[i]
    print(m[m_max_idx],m[-1])

else:
    print(p_total-m_total)
    for i,v in enumerate(p):
        if i != p_max_idx:
            print(m[0], v)
            m[0] -= v
    for i in range(len(m)):
        print(p[p_max_idx],m[i])
        p[p_max_idx] -= m[i]
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9+7
table = [0]*(N+1)
table[0] = 1

for i in range(N+1):
    if i+1<=N and (i+1) not in A:
        table[i+1] += table[i]
    if i+2<=N and (i+2) not in A:
        table[i+2] += table[i]

print(table[N]%MOD)

Fixed submission:
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9+7
table = [0]*(N+1)
table[0] = 1
broken = [1]*(N+1)
for a in A:
    broken[a] = 0

for i in range(N+1):
    if i+1<=N and broken[i+1]:
        table[i+1] += table[i]
    if i+2<=N and broken[i+2]:
        table[i+2] += table[i]

print(table[N]%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())

d = {}
for _ in range(N):
    S,T,X = map(int,input().split())
    for x in range(max(0,S-X),max(0,T-X)):
        if x in d.keys():
            d[x] = min(d[x],X)
        else:
            d[x] = X

for _ in range(Q):
    D = int(input())
    if D in d.keys():
        print(d[D])
    else:
        print(-1)

Fixed submission:
#5814544

from bisect import bisect_left

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

STX = []
D = []
for _ in range(N):
    STX.append(list(map(int,input().split())))
for _ in range(Q):
    D.append(int(input()))

STX.sort(key=lambda x:x[2])

ans = [-1]*Q
skip = [-1]*Q

for s,t,x in STX:
    left = bisect_left(D,s-x)
    right = bisect_left(D,t-x)

    while left < right:
        if skip[left] == -1:
            ans[left] = x
            skip[left] = right
            left += 1
        else:
            left = skip[left]
    
for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
X = {}
for i in map(int,input().split()):
    if i in X.keys():
        X[i] += 1
    else:
        X[i] = 1
for _ in range(M):
    b,c = map(int,input().split())
    if c in X.keys():
        X[c] += b
    else:
        X[c] = b

K = sorted(list(X.keys()),reverse=True)
res = 0
for k in K:
    if N >= X[k]:
        res += k*X[k]
        N -= X[k]
    else:
        res += k*N
        break

print(res)

Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
X = [list(map(int,input().split())) for _ in range(M)]
A.sort()
X.sort(key=lambda x:-x[1])

j = 0
for i in range(N):
    if X[j][1] < A[i]:
        break
    else:
        X[j][0] -= 1
        A[i] = X[j][1]
    if X[j][0] == 0:
        j += 1
    if j == M:
        break

print(sum(A))

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = list(map(int,input().split()))
CB = {}
for _ in range(M):
    b,c = map(int,input().split())
    if c in CB.keys():
        CB[c] += b
    else:
        CB[c] = b

A.sort()

K = sorted(list(CB.keys()),reverse=True)
L = []
for k in K:
    L += [k]*CB[k]

res = 0
for i in range(min(N,len(L))):
    if L[i] >= A[i]:
        res += L[i]
    else:
        res += sum(A[i:])
        break
else:
    res += sum(A[i+1:])

print(res)

Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
X = [list(map(int,input().split())) for _ in range(M)]
A.sort()
X.sort(key=lambda x:-x[1])

j = 0
for i in range(N):
    if X[j][1] < A[i]:
        break
    else:
        X[j][0] -= 1
        A[i] = X[j][1]
    if X[j][0] == 0:
        j += 1
    if j == M:
        break

print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
#5888164
N = int(input())
edge = [[] for _ in range(N)]
ans = [-1] * N
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v,w))
    edge[v].append((u,w))

stack = [(e,0) for e in edge[0]]
ans[0] = 0

while len(stack) > 0:
    e,c = stack.pop(0)
    n,w = e[0],e[1]
    if ans[n] >= 0:
        continue
    ans[n] = (c + w) % 2
    stack += [(e,ans[n]) for e in edge[n]]

for a in ans:
    print(a)

Fixed submission:
#5888164
N = int(input())
edge = [[] for _ in range(N)]
ans = [-1 for _ in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v,w))
    edge[v].append((u,w))

stack = [(e,0) for e in edge[0]]
ans[0] = 0

while len(stack) > 0:
    e,c = stack.pop()
    n,w = e[0],e[1]
    if ans[n] >= 0:
        continue
    ans[n] = (c + w) % 2
    stack += [(e,ans[n]) for e in edge[n]]

for a in ans:
    print(a)