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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)

    mem_key = str(n) + '-' + str(r)
    if mem_key in mem:
        return mem[mem_key]

    val = fact[n] * factinv[r] * factinv[n-r] % p
    mem[mem_key] = val
    return val

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
if K == 1:
    print(0)
    exit()

A = sorted(list(map(int, input().split())))

N = len(A)
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = 0
sum_num = 0
mem = {}
for i in range(N - (K - 1)):
    for j in range(i+K-1, N):
        ans += (A[j] - A[i]) * cmb(j-i-1, K-2, MOD) % MOD
print(ans % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

def ncr(n, r, mod=MOD):
    return (fct[n] * invf[r] * invf[n - r]) % mod


def make_tables(n, mod=MOD):
    fct = [1 for _ in range(n + 1)]
    invf = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        fct[i] = (fct[i - 1] * i) % mod
        invf[i] = divmod(fct[i])
    return fct, invf


def divmod(a, mod=MOD):
    return pow(a, mod - 2, mod)


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(N):
    A[i] %= MOD

fct, invf = make_tables(N, mod=MOD)

ans = 0
for i in range(N - K + 1):
    ans += ((A[-1-i] - A[i]) % MOD * ncr(N - i - 1, K - 1)) % MOD
print(ans % MOD)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = False
for q in qs:
    q = q.split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            S = q[2] + S
        else:
            S = S + q[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

S = input()
T = input()

out_str = "Yes"
for i in range(len(S)) :
	indexes_s = [n for n, x in enumerate(list(S)) if x == S[i]]
	indexes_t = [n for n, x in enumerate(list(T)) if x == T[i]]
	if (indexes_s == indexes_t) :
		continue
	out_str = "No"

print(out_str)

### FIXED CODE ###

S = input()
T = input()

out_str = "Yes"

indexes_s_all = []
indexes_t_all = []
for i in range(26) :
	c = chr(ord('a') + i)
	indexes_s = [n for n, x in enumerate(list(S)) if x == c]
	indexes_t = [n for n, x in enumerate(list(T)) if x == c]
	indexes_s_all.append(indexes_s)
	indexes_t_all.append(indexes_t)

indexes_s_all.sort()
indexes_t_all.sort()
if (indexes_s_all == indexes_t_all) :
	print("Yes")
else :
	print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

if n%2 == 0:
    count = 0
    for i in a:
        if a.count(i) == 2:
            count += 1
    if count == n:
        print(int(2**(n/2))%(10**9+7))
    else:
        print(0)
else:
    count = 0
    for i in a:
        if a.count(i) == 2:
            count += 1
    if count == n-1 and a.count(0) == 1:
        print(int(2**((n-1)/2))%(10**9+7))
    else:
        print(0)

### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
a.sort()
if n % 2 == 0:
    b = 0
    for i in range(0,n,2):
        if a[i] != a[i+1] and a[i] != i+1:
            b = 1
    if b == 1:
        print(0)
    else:
        print((2**(n//2))%1000000007)
else:
    b = 0
    if a[0] != 0:
        b = 1
    else:
        for i in range(1,n,2):
            if a[i] != a[i+1] and a[i] != i+1:
                b = 1
    if b == 1:
        print(0)
    else:
        print((2**(n//2))%1000000007)
### BUGGY CODE ###

#input
S = input()
Q = int(input())
P = []
for i in range(Q):
    P.append(list(map(str, input().split())))

#output
T = "AB"
for i in range(Q):
    if len(P[i]) == 1:
        T = T[-1::-1]
    else:
        v = P[i][2]
        if int(P[i][1]) == 1:
            T = v + T
        else:
            T = T + v

if "AB" in T:
    S = T.replace("AB", S)
else:
    S = T.replace("BA", S[-1::-1])
                        
print(S)

### FIXED CODE ###

#input
S = input()
Q = int(input())
P = [[]] * Q
for i in range(Q):
    P[i] = list(map(str, input().split()))

#output
flip = 0
cap = ""
tail = ""

for i in range(Q):
    if int(P[i][0]) == 1:
        flip += 1
    else:
        n = int(P[i][1])
        v = P[i][2]
        if flip % 2 == 0:
            if n == 1:
                cap = v + cap
            else:
                tail = tail + v
        else:
            if n == 1:
                tail = tail + v
            else:
                cap = v + cap

answer = ""
if flip % 2 == 0:
    answer = cap + S + tail
else:
    answer = tail[-1::-1] + S[-1::-1] + cap[-1::-1]

print(answer)
### BUGGY CODE ###

s, k = input(), int(input())
abc = [chr(i) for i in range(ord('a'), ord('a')+26)]

cnt = 0
key_lst = []
for i in abc:
    key_set = set()
    for j in range(len(s)):
        if i == s[j]:
            for l in range(j+1, len(s)+1):
                if s[j:l] not in key_set:
                    key_set.add(s[j:l])

    if cnt + len(key_set) >= k:
        key_lst = list(key_set)
        break
    else:
        cnt += len(key_set)
        k -= len(key_set)

key_lst.sort()

print(key_lst[k-1])


### FIXED CODE ###

s, k = input(), int(input())

sub_str = set()
for i in range(len(s)):
    for j in range(1, k+1):
        if i + j <= len(s):
            sub_str.add(s[i:i+j])

sub_lst = sorted(list(sub_str))
print(sub_lst[k-1])
### BUGGY CODE ###

#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
d=[[False]*w for _ in range(h)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
q=deque()
nowi=[]
ans=0

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            nowi.append((i,j))
            d[i][j]=True
q.append(nowi)
#print(nowi)
while len(q):
    nowq=q.popleft()
    nextq=[]
    #print(nowq)
    for i in nowq:
        ny,nx=i
        for yx in range(4):
            if ny+dy[yx]<0 or ny+dy[yx]>=h:
                continue
            if nx+dx[yx]<0 or nx+dx[yx]>=w:
                continue
            if d[ny+dy[yx]][nx+dx[yx]]:
                continue
            nextq.append((ny+dy[yx],nx+dx[yx]))
            d[ny+dy[yx]][nx+dx[yx]]=True
    if len(nextq):
        q.append(nextq)
        ans+=1
    #print(nextq)
print(ans)

### FIXED CODE ###

#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
d=[[False]*w for _ in range(h)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
q=deque()
nowi=[]
ans=0

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            nowi.append((i,j))
            d[i][j]=True
q.append(nowi)
#print(nowi)
while len(q):
    nowq=q.popleft()
    nextq=[]
    #print(nowq)
    for i in nowq:
        ny,nx=i
        for yx in range(4):
            if ny+dy[yx]<0 or ny+dy[yx]>=h:
                continue
            if nx+dx[yx]<0 or nx+dx[yx]>=w:
                continue
            if d[ny+dy[yx]][nx+dx[yx]]:
                continue
            nextq.append((ny+dy[yx],nx+dx[yx]))
            d[ny+dy[yx]][nx+dx[yx]]=True
    if len(nextq):
        q.append(nextq)
        ans+=1
    #print(nextq)
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
def hash(x,y):
    x,y =min(x,y),max(x,y)
    return x*10000+y
edge = defaultdict(list)
ind = defaultdict(int)
s = set()
N = int(input())
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add(hash(i,A[0]))
    for j in range(N-1):
        for k in range(j+1,N-1):
            edge[hash(i,A[j])].append(hash(i,A[k]))
            ind[hash(i,A[k])] += 1
d = deque()
nd = deque()
for hash in s:
    if ind[hash] == 0:
        d.append(hash)
ans = 0
finished = 0
while d:
    while d:
        hash = d.popleft()
        finished += 1
        for nhash in edge[hash]:
            ind[nhash] -= 1
            if ind[nhash] == 0:
                nd.append(nhash)
    d = nd
    nd = deque()
    ans += 1
if finished == N*(N-1)//2:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

from collections import defaultdict,deque
def hash(x,y):
    x,y =min(x,y),max(x,y)
    return x*(N+1)+y
s = set()
N = int(input())
edge = [[] for _ in range(N*N+N)]
ind = [0]*(N*N+N)
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add(hash(i,A[0]))
    for j in range(N-2):
            edge[hash(i,A[j])].append(hash(i,A[j+1]))
            ind[hash(i,A[j+1])] += 1
d = deque()
nd = deque()
for hash in s:
    if ind[hash] == 0:
        d.append(hash)
ans = 0
finished = 0
while d:
    while d:
        hash = d.popleft()
        finished += 1
        for nhash in edge[hash]:
            ind[nhash] -= 1
            if ind[nhash] == 0:
                nd.append(nhash)
    d = nd
    nd = deque()
    ans += 1
if finished == N*(N-1)//2:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
nl = str(n)
ll = len(nl)
lis = []
ans = 0
if ll == 1:
  print(n)
  exit()
  
def countn(a,b):
  cur = 0
  for i in range(1,n+1):
    fff=str(i)
    if int(fff[0]) == a and int(fff[-1]) == b:
      cur += 1
  return cur

for i in range(1, 10):
  for j in range(1, i+1):
    if i == j:
      ans += countn(i, j)*countn(j, i)
    else:
      ans += 2*countn(i, j)*countn(j, i)
print(ans)

### FIXED CODE ###

n = int(input())
nl = str(n)
ll = len(nl)
lis = []
ans = 0
if ll == 1:
  print(n)
  exit()
  
def countn(a,b):
  cur = 0
  if ll >= 3:
    cur += (10**(ll-2)-1)//9
    if a < int(nl[0]):
      cur += 10**(ll-2)
    elif a == int(nl[0]):
      nnl = nl[1:ll-1]
      if b > int(nl[-1]):
        cur += int(nnl)
      else:
        cur += (int(nnl)+1)
  elif ll == 2:
    if 10*a+b <= n:
      cur += 1
  if a == b:
    cur += 1
  return cur

for i in range(1, 10):
  for j in range(1, i+1):
    if i == j:
      ans += countn(i, j)*countn(j, i)
    else:
      ans += 2*countn(i, j)*countn(j, i)
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())

ans = {}
for v in itertools.combinations_with_replacement(range(1,(N//6)+1), 3):
    x,y,z = v
    fn = x**2 + y**2 + z**2 + x*y + y*z + z*x
    # if fn > N:
    #     break
    if fn in ans.keys():
        ans[fn].append([x,y,z])
    else:
        ans[fn] = [[x,y,z]]


for i in range(1,N+1):
    if i in ans.keys():
        count = 0
        for j in ans[i]:
            x,y,z = j
            if x == y == z:
                count += 1
            else:
                count += 3
        # print(i, count, ans[i])
        print(count)
    else:
        # print(i, 0)
        print(0)


### FIXED CODE ###

N = int(input())
ans = [0 for _ in range(1,10101)]

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n < N+1:
                ans[n-1] += 1

print(*ans[:N],sep='\n')
### BUGGY CODE ###

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

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                start = S[tmp - 1]
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                start = S[tmp + 1]
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                start = S[tmp + 1]
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                start = S[tmp - 1]
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

print(ans)


### FIXED CODE ###

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

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                start = S[tmp - 1]
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                start = S[tmp + 1]
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                start = S[tmp + 1]
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                start = S[tmp - 1]
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

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


def main():

    A,B = map(int,input().split())
    if A==0 or B==0:
        print("IMPOSSIBLE")
        exit()
    if A%2!=B%2:
        print("IMPOSSIBLE")
        exit()


    K=0
    tmp =A
    A 
    while(True):

        if abs(A-K)==abs(B-K):
            print(K)
            exit()
        K += 1



if __name__== "__main__":
    main() 


### FIXED CODE ###


def main():

    A,B = map(int,input().split())
    if A==0 or B==0:
        print("IMPOSSIBLE")
        exit()
    if A%2!=B%2:
        print("IMPOSSIBLE")
        exit()

    small = min(A,B)
    large = max(A,B)
    large -= small
    print(int(large/2+small))




if __name__== "__main__":
    main()
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
visited = [now]
while A[now] not in visited:
    visited.append(A[now])
    now = A[now]
looplen = len(visited)-visited.index(A[now])
if K < len(visited):
    print(visited[K]+1)
else:
    print(visited[visited.index(A[now])+(K-len(visited))%looplen]+1)

### FIXED CODE ###

#!/usr/bin/env python3
import sys

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    count = 1
    now = 0
    visited = [1]
    set_v = set()
    set_v.add(1)
    l = -1
    while count < N:
        x = A[now]
        if x in set_v:
            l = visited.index(x)
            break
        else:
            count += 1
            visited.append(x)
            set_v.add(x)
            now = x-1
    r = count
    # print(l,r,visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)])

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

x=input().split()
n=int(x[0])
k=int(x[1])

def fast_expo(b,n,p):
    if n==0:
        return 1
    if n==1:
        return b%p
    if n%2==0:
        return fast_expo(((b%p)*(b%p))%p,n//2,p)
    else:
        return (b*fast_expo(((b%p)*(b%p))%p,n//2,p))%p
def combi(n,k,p):
    X=1
    Y=1
    for i in range(k):
        X=(X*(n-i))%p
        Y=(Y*(k-i))%p
    Z=fast_expo(Y,p-2,p)
    return (X*Z)%p

p=10**9+7
s=0
L=min(n,k+1)
for i in range(L):
  s=(s+(combi(n,i,p)*combi(n-1,i,p))%p)%p
print(s)  


### FIXED CODE ###

x=input().split()
n=int(x[0])
k=int(x[1])
def fact_inverse(n,p):
    fact=[1]*(n+1)
    inv=[1]*(n+1)
    inv_fact=[1]*(n+1)
    inv[0]=0
    inv_fact[0]=0
    for i in range(2,n+1):
        fact[i]=(fact[i-1]*i)%p
        #compute the inverse of i mod p
        inv[i]=(-inv[p%i]*(p//i))%p
        inv_fact[i]=(inv_fact[i-1]*inv[i])%p
    return fact,inv_fact    
    

def combi2(n,p):
    f,inv=fact_inverse(n,p)
    combis=[1]*(n+1)
    for k in range(1,n+1):
        if k >=n//2+1:
            combis[k]=combis[n-k]
        else:
            combis[k]=(((f[n]*inv[n-k])%p)*inv[k])%p
    return combis    
      
    
p=10**9+7
combis1=combi2(n,p)
combis2=combi2(n-1,p)
s=0
L=min(n,k+1)
for i in range(L):
  s=(s+(combis1[i]*combis2[i])%p)%p
print(s)
### BUGGY CODE ###

from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
maps = [[j=="#" for j in input()] for i in range(H)]
q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])

count = 0
for i in range(H*W):
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
      nx = x+dx
      ny = y+dy
      if H > nx >= 0 and W > ny >= 0 and maps[nx][ny] != True:
        maps[nx][ny] = True
        nq.append([nx,ny])
  if nq:
    q = copy.copy(nq)
  else:
      break
  count += 1
print(i)

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N = int(input())
T = 100
for i in range(1,N+1):
    if N%i ==0:
        A = i
        B = N/i
        Q = len(str(max(A, B)))
        T = min(T,Q)
print(T)


### FIXED CODE ###

import math
N = int(input())
T = 100
for i in range(1,(math.ceil(N**0.5))+1):
    if N%i ==0:
        A = int(i)
        B = int(N/i)
        Q = len(str(max(A, B)))
        T = min(T,Q)
print(T)
### BUGGY CODE ###

#!/usr/bin/env python3
import copy


class UnionFind:
    __slots__ = ['id', 'sz']

    def __init__(self, n):
        self.id = [-1] * n
        self.sz = n

    def root(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.root(self.id[x])
            return self.id[x]

    def find(self, x, y):
        return uf.root(x) == uf.root(y)

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz -= 1
            return True
        return False


n = int(input())
uvw = [list(map(int, input().split())) for i in range(n-1)]
groop = [-1]*n
groop[0] = 1
l = [0, 1]
uf = UnionFind(n)
uvw.sort()
while uvw:

    nextlist = []
    for u,v,w in uvw:
        if groop[u-1] >= 0:
            if w % 2:
                groop[v-1] = l[l.index(groop[u-1])-1]
            else:
                groop[v-1] = groop[u-1]
        elif groop[v-1] >= 0:
            if w % 2:
                groop[u-1] = l[l.index(groop[v-1])-1]
            else:
                groop[u-1] = groop[v-1]
        else:
            nextlist.append((u, v, w))
    uvw = copy.deepcopy(nextlist)
for g in groop:
    print(1 if g else 0)


### FIXED CODE ###

#!/usr/bin/env python3
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]
graph=[[] for i in range(n+1)]
color=[-1]*(n+1)
for u,v,w in uvw:
    graph[u].append((v,w))
    graph[v].append((u,w))

color[1]=1
ne=[1]
while ne:
    t=ne.pop()
    for v,w in graph[t]:
        if color[v]==-1:
            ne.append(v)
            color[v]=color[t] if w%2==0 else (color[t]+1)%2

for i in range(1,n+1):
    print(color[i])