Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N=int(input())
A=[]
B=[]
takahashi=0
aoki=0
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
for i in range(N):
    if not B or not A:
        break
    if max(A)>=max(B):
        num=A.index(max(A))
        takahashi+=A[num]
        del A[num]
        del B[num]
    else:
        num=B.index(max(B))
        takahashi+=A[num]
        del A[num]
        del B[num]
    if not B or not A:
        break
    if max(B)>=max(A):
        num=B.index(max(B))
        aoki+=B[num]
        del A[num]
        del B[num]
    else:
        num=A.index(max(A))
        aoki+=B[num]
        del A[num]
        del B[num]
print(takahashi-aoki)

### FIXED CODE ###

N=int(input())
AB=[]
takahashi=0
aoki=0
for i in range(N):
    a,b=map(int,input().split())
    AB.append([a,b,a+b])
AB.sort(key=lambda AB:(AB[2],AB[1],AB[0]),reverse=True)
for i in range(N):
    if i%2==0:
        takahashi+=AB[i][0]
    else:
        aoki+=AB[i][1]
print(takahashi-aoki)
### BUGGY CODE ###

N,K = map(int,input().split())
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
ans = 0
sum_head = sum(head)
l_head = len(head)
l_no_head = len(no_head)
for i in range(n+1):
    ans = max(ans,sum_head+sum(no_head[:l_no_head-i])+sum(unused_head[:i]) + (l_head+i)**2)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
sum_head = sum(head)
sum_no_head = sum(no_head)
sum_unused_head = 0
l_head = len(head)
l_no_head = len(no_head)
ans = sum_head + sum_no_head + l_head ** 2
for i in range(n):
    sum_no_head -= no_head[-1-i]
    sum_unused_head += unused_head[i]
    ans = max(ans,sum_head+sum_no_head+sum_unused_head + (l_head+i+1)**2)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
array = []
for i in range(n):
    a, b = map(int, input().split())
    for j in range(b):
        array.append(a)
array.sort()
print(array[k-1])


### FIXED CODE ###

n, k = map(int, input().split())
number = [[0,0] for i in range(n)]
for i in range(n):
    number[i] = list(map(int, input().split()))
number.sort(key=lambda x:(x[0],x[1]))
count = 0
result = 0
for el in number:
    count += el[1]
    if count >= k:
        result = el[0]
        break
print(result)
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]
P =  [int(n) for n in input().split()]
o = {}
for i in range(1,1001):
    o[i] = sum([(j/i) for j in range(1,i+1)])
ans = 0
for k in range(N-K+1):
    m = sum([o[x] for x in P[k:k+K]])
    if m > ans:
        ans = m
print(ans)
    

### FIXED CODE ###

N, K = [int(n) for n in input().split()]
P = [(int(n)+1)/2 for n in input().split()]
ans = sum(P[:K])
e = ans
for p,x in zip(P, P[K:]):
    e = e-p+x
    if ans < e:
        ans = e
print(ans)
### BUGGY CODE ###

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


B = sorted(list(set(A)), reverse=True)

for i in range(len(B)):
    b = B[i]
    n = A.count(b)
    if n >= 2:
        if n >= 4:
            print(b*b)
            exit()
        else:
            C = B[i+1:]
            for c in C:
                if  A.count(c) >= 2:
                    print(b*c)
                    exit()

print(0)


### FIXED CODE ###

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

x = 0
y = 0
S = set()

for a in A:
    if a in S:
        if a < x:
            continue
        elif a > y:
            x = y
            y = a
        else:
            x = a
        S.remove(a)
    else:
        S.add(a)

print(x*y)
### BUGGY CODE ###

n,k=map(int,input().split())
A=sorted(list(map(int,input().split())))
F=sorted(list(map(int,input().split())),reverse=True)
ng=-1
ok=10**12+10
while ok-ng>1:
  mid=(ok+ng)//2
  a=0
  for i in range(n):
    a=a+max(0,A[i]-mid//F[i])
  if a>k:
    ng=mid
  else:
    ok=mid
print(ok)

### FIXED CODE ###

n,k=map(int,input().split())
A=sorted(list(map(int,input().split())))
F=sorted(list(map(int,input().split())),reverse=True)
ng=-1
ok=10**12+10
while ok-ng>1:
  mid=(ok+ng)//2
  a=0
  for i in range(n):
    a=a+max(0,A[i]-mid//F[i])
  if a>k:
    ng=mid
  else:
    ok=mid
print(ok)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    mat = dijkstra(csr_matrix((np.ones(M), (a, b)), shape=(N+1, N+1), dtype=np.int32), indices=1, directed=False, limit=2)
    return YES if mat[N] <= 2 else NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# cython: profile=True
import sys

YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    AB = sorted(zip(a, b))
    s = set([b for a, b in AB if a == 1])
    g = set([a for a, b in AB if b == N])
    return YES if s & g else NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

def test():
    import doctest
    doctest.testmod()

def perf():
    import cProfile
    cProfile.run("main()")

if __name__ == '__main__':
    #test()
    #perf()
    main()
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i, v):
            x = i+1
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    if n == 1:
        print(a[0])
        return
    ok = 0
    ng = 10**9+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        b = [0]+list(ac([(i >= mid)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            ok = mid
        else:
            ng = mid
    print(ok)


main()


### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i, v):
            x = i+1
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    def value(v):
        if n == 1:
            if v <= a[0]:
                return True
            else:
                return False
        b = [0]+list(ac([(i >= v)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            return True
        else:
            return False

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(b_search(0, 10**9+1, value))


main()
### BUGGY CODE ###

K, S = map(int,input().split())

count = 0
for i in range(0,K+1):
    if i > S:
        continue
    for j in  range(0,K+1):
        if j > S:
            continue
        for k in  range(0,K+1):
            if i+j > S:
                continue
            if i + j + k == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int,input().split())

count = 0
for i in range(0,K+1):
    if i > S:
        continue
    for j in  range(0,K+1):
        if 0 <= (S - i - j) <= K:
            count += 1

print(count)
### BUGGY CODE ###

import sys

class UnionFind():
    def __init__(self, num, V):
        self.par = [-1]*num
        self.size = [1]*num
        self.unused = [0]*num
        self.cost = V
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return 0
        rx, ry = sorted((rx, ry))
        self.par[ry] = rx
        #self.size[rx] += self.size[ry]
        self.cost[rx] += self.cost[ry]
        self.unused[rx] += self.unused[ry]
        self.unused[ry] = 0
        return 1

def inpl() : return list(map(int, input().split()))
input = sys.stdin.readline

N, M = inpl()
X = inpl()
Edge = []
for _ in range(M):
    a, b, y = inpl()
    a -= 1
    b -= 1
    Edge.append((y, a, b))

Edge.sort()
Tr = UnionFind(N, X)
for y, a, b in Edge:
    Tr.union(a, b)
    pa = Tr.find(a)
    if Tr.cost[pa] >= y:
        Tr.unused[pa] = 0
    else:
        Tr.unused[pa] += 1

print(sum(Tr.unused))

### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self, num, V):
        self.par = [-1]*num
        #self.size = [1]*num
        self.unused = [0]*num
        self.cost = V
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return 0
        if ry > rx:
            rx, ry = ry, rx
        self.par[ry] = rx
        #self.size[rx] += self.size[ry]
        self.cost[rx] += self.cost[ry]
        self.unused[rx] += self.unused[ry]
        self.unused[ry] = 0
        return 1

def solve():
    
    N, M = map(int, input().split())
    X = list(map(int, sys.stdin.readline().split()))
    Edge = [None]*M
    for i in range(M):
        a, b, y = list(map(int, sys.stdin.readline().split()))
        Edge[i] = (y, a-1, b-1)
    
    Edge.sort()
    Tr = UnionFind(N, X)
    for y, a, b in Edge:
        Tr.union(a, b)
        pa = Tr.find(a)
        if Tr.cost[pa] >= y:
            Tr.unused[pa] = 0
        else:
            Tr.unused[pa] += 1
    
    print(sum(Tr.unused))
    return

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

from functools import lru_cache
 
@lru_cache(maxsize=100000)
def n_th_prime(n):
    if n == 0:
        return 2
    z = n_th_prime(n-1) + 1
    while True:
        for i in range(n):
            if z % n_th_prime(i) == 0:
                break
        else: return(z)
        z += 1

x = int(input())

k=0
while True:
    a = n_th_prime(k)
    if x > a:
        k += 1
    else:
        print(a)
        break


### FIXED CODE ###

from functools import lru_cache
 
@lru_cache(maxsize=100000)
def n_th_prime(n):
    if n == 0:
        return 2
    primes = [n_th_prime(k) for k in range(n)]
    k = 1
    x = primes[-1] + 1
    while True:
        for p in primes[:k]:
            if x % p == 0:
                x += 1
                break
        else:
            if x > p**2:
                k += 1
            else:
                return x

x = int(input())

k = 0
p = 2
while True:
    for i in range(k):
        p = n_th_prime(i)
        if x % p == 0:
            x += 1
            break
    else:
        if x > p**2:
            k += 1
        else:
            print(x)
            break
### BUGGY CODE ###

import numpy as np

Input = map(int,raw_input().split(' '))
N = Input[0]
K = Input[1]
A = map(int,raw_input().split(' '))
#A = sorted(A)

count = []
for n in range(1,N+1):
	count.append(A.count(n))
count = sorted(count)
zeroCount = count.count(0)
count = np.array(count)
rslt = 0
if zeroCount > N - K :
	print rslt
else:
	rslt += count[zeroCount:N-K].sum()
	print rslt

### FIXED CODE ###

import bisect
Input = map(int,raw_input().split(' '))
N = Input[0]
K = Input[1]
A = map(int,raw_input().split(' '))
A = sorted(A)
count = []
i = 0
while i < len(A):
	count.append(bisect.bisect_right(A,A[i]) - bisect.bisect_left(A,A[i]))
	i = bisect.bisect_right(A,A[i])
count = sorted(count)
dim = len(count)
rslt = 0
if dim <= K:
	print rslt
else:
	rslt += sum(count[:dim-K])
	print rslt
### BUGGY CODE ###

import sys,collections
input = sys.stdin.readline

n = int(input())
l = [[] for _ in range(n+1)]
nn = []
cnt = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)
    cnt[a] += 1
    cnt[b] += 1

m = max(cnt) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
l=[[]]
nn = []
for _ in range(n+1):
    l.append([])

for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

ml = list(map(len,l)) 
m = max(ml)
co = []
for i in range(n+1):
    co.append( set(range(1,ml[i]+1) ))

col = [0]*(n+1)
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])
### BUGGY CODE ###

n = int(input())

d = []
for i in range(n):
    command = input().split()
    if command[0] == 'insert':
        d.append(command[1])
    else:
        print('yes' if command[1] in d else 'no')

### FIXED CODE ###

n = int(input())

d = set()
for i in range(n):
    com = input().split()
    if com[0] == 'insert':
        d.add(com[1])
    else:
        print('yes' if com[1] in d else 'no')
### BUGGY CODE ###

def solve():
    from bisect import bisect_left, bisect_right

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

    As.sort()
    negAs = [-A for A in As[::-1]]
    A2s = [A*A for A in As]
    A2s.sort()

    pstvBs = []
    numB0= 0
    ngtvBs = []
    for A in As:
        if A > 0:
            pstvBs.append(A)
        elif A == 0:
            numB0 += 1
        else:
            ngtvBs.append(A)

    def isOK(x):
        if x >= 0:
            dire = 1
        else:
            dire = -1
        num = 0
        # 正
        iA = 0
        for B in pstvBs[::-dire]:
            key = x//B
            while iA < N and As[iA] <= key:
                iA += 1
            num += iA
        # ゼロ
        if x >= 0:
            num += N*numB0
        # 負
        iA = 0
        for B in ngtvBs[::dire]:
            key = x//(-B)
            while iA < N and negAs[iA] <= key:
                iA += 1
            num += iA
        i = bisect_right(A2s, x)
        num -= i
        num //= 2
        return num >= K

    ng, ok = -(10**18)-1, 10**18+1
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()


### FIXED CODE ###

def solve():
    from bisect import bisect_left, bisect_right

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

    As.sort()
    negAs = [-A for A in As[::-1]]
    A2s = [A*A for A in As]
    A2s.sort()

    pstvBs = []
    numB0= 0
    ngtvBs = []
    for A in As:
        if A > 0:
            pstvBs.append(A)
        elif A == 0:
            numB0 += 1
        else:
            ngtvBs.append(A)

    def isOK(x):
        if x >= 0:
            dire = 1
        else:
            dire = -1
        num = 0
        # 正
        iA = 0
        for B in pstvBs[::-dire]:
            key = x//B
            while iA < N and As[iA] <= key:
                iA += 1
            num += iA
        # ゼロ
        if x >= 0:
            num += N*numB0
        # 負
        iA = 0
        for B in ngtvBs[::dire]:
            key = x//(-B)
            while iA < N and negAs[iA] <= key:
                iA += 1
            num += iA
        i = bisect_right(A2s, x)
        num -= i
        num //= 2
        return num >= K

    ng, ok = -(10**18)-1, 10**18+1
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
que = deque([int(input()) for i in range(N)])
tmp = 0

for i in range(N):
    tmp = que.popleft()
    print(max(que))
    que.append(tmp)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
que = deque([int(input()) for i in range(N)])
tmp = 0
max_num1 = sorted(que)[-1]
max_num2 = sorted(que)[-2]

for i in range(N):
    tmp = que.popleft()
    if tmp != max_num1:
        print(max_num1)
    else:
        print(max_num2)
    que.append(tmp)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = []
b = 0

for temp in q:
    if temp[0] == 1:
        a.insert(bisect_left(a, temp[1]), temp[1])
        b += temp[2]
    else:
        #print(a)
        m = a[len(a) // 2 + len(a) % 2 - 1]
        ans = b
        for x in a:
            ans += abs(m - x)
        print(m, ans)


### FIXED CODE ###

from heapq import heappop, heappush, heappushpop

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

ans = 0

heappush(L, -q[0][1])

for i in range(1, n):
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            ans += abs(temp[1] + L[0])
            p = heappushpop(L, - temp[1])
            heappush(R, - p)
        else:
            ans += abs(temp[1] + L[0])
            tl = L[0]
            p = heappushpop(R, temp[1])
            heappush(L, - p)
            if tl != L[0]:
                ans -= abs(tl - L[0])
        b += temp[2]
    else:
        m = - L[0]
        print(m, ans + b)
### BUGGY CODE ###

N=int(input())
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())
stay_a=N
stay_b=0
stay_c=0
stay_d=0
stay_e=0
stay_f=0
for i in range(100000000000000):
  delta_a=min(stay_a,A)
  stay_a=stay_a-delta_a
  delta_b=min(stay_b,B)
  stay_b=stay_b-delta_b
  delta_c=min(stay_c,C)
  stay_c=stay_c-delta_c
  delta_d=min(stay_d,D)
  stay_d=stay_d-delta_d
  delta_e=min(stay_e,E)
  stay_e=stay_e-delta_e
  stay_b+=delta_a
  stay_c+=delta_b
  stay_d+=delta_c
  stay_e+=delta_d
  stay_f+=delta_e
  if stay_f==N:
    break
print(1+i)

### FIXED CODE ###

N=int(input())
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())
stay_a=N
stay_b=0
stay_c=0
stay_d=0
stay_e=0
stay_f=0
f = -(-N//min(A,B,C,D,E))
print(4+f)
### BUGGY CODE ###

n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()))
# 広義単調減少部分列の最長を求める

## dp[i] := num_listのi番目までの数字が末尾となるような文字列の長さの最大 と定義すると
# 1.num_list[i]番目のみ
# 2.num_list[j] >= num_list[i] を満たす num_list[j] で終わる文字列の末尾にnum_list[i] をつける
# 1 もしくは 2をみたすものの中で最大のものがdp[i]

dp = [0] * n
dp[0] = 1

for i in range(1, n):
    add_previous = [0] # 2の条件を満たすものを入れる
    for j in range(0, i):
        if num_list[i] <= num_list[j]:
            add_previous.append(dp[j] + 1)
       
    dp[i] = max([1, max(add_previous)])
    
print(max(dp))

### FIXED CODE ###

import bisect

n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()) * -1) 

dp = [1] * n 

for i in num_list:
    indx = bisect.bisect_right(dp, i)
    dp[indx] = min(dp[indx], i)

ans = sum(x < 1 for x in dp)

print(ans)
### BUGGY CODE ###

n = int(input())

uvws = [list(map(int, input().split())) for _ in range(n-1)]
uvws.sort(key=lambda x: x[0])

zeros = {1}
ones = set()

while len(zeros) + len(ones) < n:
    for uvw in uvws:
        u, v, w = uvw
        if u not in zeros and u not in ones and v in zeros:
            if w % 2:
                ones.add(u)
            else:
                zeros.add(u)
        if u not in zeros and u not in ones and v in ones:
            if w % 2:
                zeros.add(u)
            else:
                ones.add(u)

        if v not in zeros and v not in ones and u in zeros:
            if w % 2:
                ones.add(v)
            else:
                zeros.add(v)
        if v not in zeros and v not in ones and u in ones:
            if w % 2:
                zeros.add(v)
            else:
                ones.add(v)

for i in range(1, n+1):
    print(1 if i in ones else 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def tree_path():
    # 辺と長さが与えられる
    # 頂点1からの各点の距離を計算する
    # 距離が偶数か奇数かで色分け
    sys.setrecursionlimit(100000)
    n = int(input())
    path = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append((v, w))
        path[v].append((u, w))
    # d[0]は使わない
    d = [-1] * (n + 1)

    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for x, w in path[i]:
                walk(x, c + w)

    walk(1, 0)
    for i in d[1:]:
        print(i % 2)

        
tree_path()