Harryxun/stf_run huggingface dataset:
import math
n,a,b,k= map(int,input().split())	
def w(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#コンビネーション


c = 0
if k//a >= n:
    x = n
else:
    x = k //a
for h in range(0,x+1):
    i = (k-a*h)/b
    
    if 2*n >= h + int(i) and i == int(i):
        c = w(n,h)*w(n,int(i))+c
if c == 0:
    c = 1
print(c%998244353)

### FIXED CODE ###

mod = 998244353

n,a,b,k = map(int,input().split())

fact = [1]
fact_inv = [1]
for i in range(n+4):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod


res = 0

for i in range(n+1):
    if k - a*i < 0:
        continue
    
    if (k-a*i)%b != 0:
        continue

    j = (k-a*i)//b

    if j > n:
        continue

    res = (res + mod_comb_k(n,j,mod)*mod_comb_k(n,i,mod)%mod)%mod

print(res%mod)
N = int(input())
import sympy
ans=0
for i in range(1,N):
    ans+=sympy.divisor_count(i)
print(ans)

### FIXED CODE ###

N = int(input())
ans=0
for i in range(1,10**6+1):
    for j in range(1,1000001):
        if i*j>N-1:
            break
        else:
            ans+=1
print(ans)
#AGC-040
S = input()
A = [0] * (len(S) + 1)

def check_left(n, S):
    count = 0
    for i in reversed(range(0, n)):
        if S[i] == "<":
            count += 1
        else:
            break
    return count

def check_right(n, S):
    count = 0
    for i in range(n, len(S)):
        if S[i] == ">":
            count += 1
        else:
            break
    return count

A[0] = max(check_left(i, S), check_right(i, S))

for i in range(1, len(S)+1):
    if A[i-1] != 0:
        if S[i-1] == "<":
            A[i] = A[i-1] + 1
        else:
            if S[i] == "<":
                A[i] = 0
            else:
                A[i] = max(check_left(i, S), check_right(i, S))
    else:
        A[i] = max(check_left(i, S), check_right(i, S))

print(sum(A))

### FIXED CODE ###

S = input()
N = len(S) + 1
 
A = [0] * N
 
if S[0] == '<':
    A[0] = 0

if S[-1] == '>':
    A[-1] = 0

for i in range(1, N-1):
    if S[i-1] == '>' and S[i] == '<':
        A[i] = 0

for i in range(N-1):
    if S[i] == '<':
        A[i+1] = A[i] + 1

for i in range(N-1)[::-1]:
    if S[i] == '>':
        A[i] = max(A[i], A[i+1] + 1)

print(sum(A))
A, B = map(int, input().split())

lst = []
for i in range(1, min(A, B)+1):
    if A % i == 0 and B % i == 0:
        lst.append(i)
        
from math import gcd

ans = 0
cnt = 1

for j in range(1, len(lst)):
    for k in range(j+1, len(lst)):
        if gcd(lst[j], lst[k]) == 1:
            cnt += 1
        else:
            if cnt > ans:
                ans = cnt
                cnt = 0
            
print(ans+1)

### FIXED CODE ###

A, B = map(int, input().split())

import math

if A < B:
    A, B = B, A
    
while A % B != 0:
    A, B = B, A%B
    
ans = 1

for i in range(2, int(math.sqrt(B))+1):
    if B % i == 0:
        ans += 1
        
        while B % i == 0:
            B //= i
            
if B > 1:
    ans += 1
    
print(ans)
import math
from functools import reduce

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

print(reduce(math.gcd, A))

### FIXED CODE ###

from fractions import gcd

n = int(input())
A = [int(i) for i in input().split()]

a = A[0]
for i in range(1,n):
    a=gcd(a, A[i])

print(a)
a = map(int,input().split())
a.sort()
if a[0] == 5:
  if a[1] == 7:
    if a[2] == 5:
      print("YES")
print("NO")

### FIXED CODE ###

a = list(map(int,input().split()))
a.sort()
if a[0] == 5 and a[1] == 5 and a[2] == 7:
  print("YES")
else:
  print("NO")
h, w = map(int, input().split())
s = [input().split() for _ in range(h)]
al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(h):
  for j in range(w):
    if s[i][j] = "snuke":
      print("{}{}".format(al[i], j+1))
      exit()
    else:
      pass

### FIXED CODE ###

h, w = map(int, input().split())
s = [input().split() for _ in range(h)]
al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(h):
  for j in range(w):
    if s[i][j] == "snuke":
      print("{}{}".format(al[j], i+1))
      exit()
    else:
      pass
a = int(input())
b = []
for i in range(a + 1):
  if i % 3 == 0:
    pass
  elif i 5 5 == 0:
    pass
  else:
    b.append(i)
c = sum(b)
print(c)

### FIXED CODE ###

a = int(input())
b = []
for i in range(a + 1):
  if i % 3 == 0:
    pass
  elif i % 5 == 0:
    pass
  else:
    b.append(i)
c = sum(b)
print(c)
import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = tuple(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

ans = [-1] * (N + 1)
inf = 10**8
LIS = [inf] * (N + 10)


def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, s)
    # 頂点sでの結果をもとに戻す
    LIS[i] = v
    return


DFS(1)
print(*ans[1:], sep="\n")

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = tuple(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 10)


def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, s)
    # 頂点sでの結果をもとに戻す
    LIS[i] = v
    return


DFS(1)
print(*ans[1:], sep="\n")
A = int(input())
B = int(input())
X = A + B
Y = A - B
Z = A * B
listo = []
listo.append(X)
listo.append(Y)
listo.append(Z)
print(max(listo))

### FIXED CODE ###


S = input().split()
X = int(S[0])+int(S[1])
Y = int(S[0])-int(S[1])
Z = int(S[0])*int(S[1])
if X >= Y:
    if X >= Z:
        print(X)
    else:
        print(Z)
else:
    if Y >= Z:
        print(Y)
    else:
        print(Z)
a,b=input().split()
if a==b:
  print("EQUAL")
elif a<b:
  print("LESS")
else:
  print("GREATER")

### FIXED CODE ###

a=input()
b=input()
if len(a)==len(b):
  if a==b:
    print("EQUAL")
  elif a<b:
    print("LESS")
  else:
    print("GREATER")
elif len(a)<len(b):
  print("LESS")
else:
  print("GREATER")
import sys
N = int(input())
Data = []
for _ in range(N):
    x,y,h = map(int,input().split())
    if h != 0:
        Data.append([x,y,h])

Data.sort(key=lambda x:x[2],reverse=True)

for cx in range(101):
    for cy in range(101):
        found = True
        ans   = -1
        for i in range(0,N):
            x,y,h = Data[i]
            if i == 0:
                ans = h + abs(x-cx)+abs(y-cy)
            else:
                ph = h + abs(x-cx)+abs(y-cy)
                if ans != ph:
                    found = False
                    break
        if found == True:
            print( '{} {} {}'.format(cx,cy,ans))
            sys.exit()

### FIXED CODE ###

import sys
N = int(input())
Data = []
for _ in range(N):
    x,y,h = map(int,input().split())
    Data.append([x,y,h])

Data.sort(key=lambda x:x[2],reverse=True)

for cx in range(101):
    for cy in range(101):
        found = True
        ans   = -1
        for i in range(N):
            x,y,h = Data[i]
            if i == 0:
                # h != 0
                ans = h + abs(x-cx)+abs(y-cy)
            else: 
                diff = ans - abs(x-cx)-abs(y-cy)
                if  diff < 0:
                    if h != 0:
                        found = False
                        break
                else: 
                    if diff != h:
                        found = False
                        break
        if found == True:
            print( '{} {} {}'.format(cx,cy,ans))
            sys.exit()
from itertools import product
from math import log2

N = int(input())
X = input()
m = sum(list(map(int, X)))+1
n = int(log2(m)+1)
f = [0]

i = 0
for p in product([0,1], repeat=n):
    if i>0:
        a = sum(p)
        f.append(f[i%a]+1)
    i += 1

for i in range(N):
    if X[i] == '1':
        x = int(X[0:i]+'0'+X[i+1:], 2)
        a = m-2
    else:
        x = int(X[0:i]+'1'+X[i+1:], 2)
        a = m
    print(f[x%a]+1)

### FIXED CODE ###

N = int(input())
X_2 = input()
X_10 = int(X_2, 2)

y = X_2.count('1')

a = X_10%(y+1)
if y==1:
    b = 0
else:
    b = X_10%(y-1)

for i in range(N):
    if X_2[i] == '1' and y == 1:
        print(0)
        continue
    elif X_2[i] == '1':
        x = (b-pow(2, N-1-i, y-1))%(y-1)
    else:
        x = (a+pow(2, N-1-i, y+1))%(y+1)
    count = 1
    while x!=0:
        x %= bin(x)[2:].count('1')
        count += 1
    print(count)
n = int(input())
h = list(map(int, input().split()))
h = h[::-1]
ans = []
x = 0
if n > 1:
    for i in range(1,n):
        if h[i-1] <= h[i]:
            x += 1
        else:
            ans.append(x)
            x = 0
else:
    ans.append(0)
print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
h = h[::-1]
ans = []
x = 0
if n > 1:
    for i in range(1,n):
        if h[i-1] <= h[i]:
            x += 1
        else:
            ans.append(x)
            x = 0
    ans.append(x)
else:
    ans.append(0)
print(max(ans))
def resolve():
    n = int(input())
    woker = list(map(int, input().split()))
    woker_count = collections.Counter(woker)
    for i in range(n):
        print(woker_count[i + 1])


resolve()

### FIXED CODE ###

import collections


def resolve():
    n = int(input())
    woker = list(map(int, input().split()))
    woker_count = collections.Counter(woker)
    for i in range(n):
        print(woker_count[i + 1])


resolve()
List=input().split()
a=int(List[1])
b=int(List[2])

if b>2*a:
    c=b-2*a
    d=c//4
    print(a+d)
else:
    print(b//2)

### FIXED CODE ###

List=[int(j) for j in input().split()]
a=List[0]
b=List[1]

if b>2*a:
    c=b-2*a
    d=c//4
    print(a+d)
else:
    print(b//2)
print(((input())/3)**3)

### FIXED CODE ###

print(((int(input()))/3)**3)
S = input()
Q = int(input())
counter =0

for q in range(Q):
    inpu_ = input()
    if len(inpu_)==1:
        counter += 1
    else:
        a,f,c = map(str,inpu_.split())
        if f=="1":
            if counter%2 == 1:
                S = S+c
            else:
                S = c+S

        else:
            if counter%2==1:
                S = c+S
            else: 
                S = S+c

if counter%2==1:
    S.reverse()
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
flag = True
from collections import deque
que=deque(S)

for i in range(Q):
    a = input().split()
    if a[0]=="1":
        flag = not flag

    else:
        f = a[1]
        c = a[2]
        if f=="1":
            if flag:
                que.appendleft(c)
            else:
                que.append(c)
        else:
            if flag:
                que.append(c)
            else:
                que.appendleft(c)

if not flag:
    que.reverse()

print("".join(que))
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            deq.append(node)
    if(len(deq) > 0):
        next_node = deq.pop()
        BST(next_node, deq, dist)
    else:
        return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)


### FIXED CODE ###

from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)
X, N = [int(x) for x in input().split()]

def main(X, N):
    if N == 0:
        return X
    arrp = [int(x) for x in input().split()]
    b = sorted(arrp)
    lists = []
    for x in range(1, 101):
        if x not in arrp:
            a = abs(X-x)
            if a != 0:
                lists.append([a, x])
    return sorted(lists)[0][1]

print(main(X, N))

### FIXED CODE ###

X, N = [int(x) for x in input().split()]

def main(X, N):
    if N == 0:
        return X
    arrp = [int(x) for x in input().split()]
    minus = X
    plus = X
    while True:
        if minus not in arrp:
            print(minus)
            exit()
        if plus not in arrp:
            print(plus)
            exit()
        minus -= 1
        plus += 1

print(main(X, N))
n,x = map(int,input().split())
m = sorted([int(input()) for i in range(n)])
newx = x - sum(m)
c = n

for j in range(100):
  for i in m:
    newx -= i
    c +=1
    if newx < x - sum(m):
      break
if newx < x - sum(m):
  break
    
print(c-1)

### FIXED CODE ###

a = input().count("o")
print(700 + int(a)*100)
n = int(input())
a = list(map(int,input().split()))
A = sum(a[:n-1:])-a[n]
c = 10*9
c = min(c,A)
if n == 2:
    print(abs(a[0]-a[1]))
else:
    for i in range(1,n-1):
        A=A-2*a[n-i]
        c = min(c,abs(A))
    print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
A = sum(a[:n-1])-a[n-1]
c = n*(10**9)
c = min(c,abs(A))
if n == 2:
    print(abs(a[0]-a[1]))
else:
    for i in range(1,n-2):
        A=A-2*a[n-1-i]
        c = min(c,abs(A))
    print(c)
import numpy as np
N=int(input())
x=[105, 135, 165, 189, 195]

X=[N-x[i] for i in range(len(x))]
XX=np.where(np.array(X) < 0) 
if N<195:
  print(XX[0][0])
  else:
    print(5)

### FIXED CODE ###

import numpy as np
N=int(input())
x=[105, 135, 165, 189, 195]

X=[N-x[i] for i in range(len(x))]
XX=np.where(np.array(X) < 0) 
if N<195:
  print(XX[0][0])
else:
  print(5)
import itertools
s = input()
count = 0

for i,j in itertools.combinations(range(0,len(str(s))+1),2):
    if int(s[i:j]) % 2019 ==0:
        count +=1
    print(s[i:j])
print(count)
    

### FIXED CODE ###

s , w = map(int, input().split())

if w>=s:
    print("unsafe")
else:
    print("safe")
xs = [int(input()) for i in range[5]]
k = int(input())
if (xs[4] - xs[0] <= k):
	print("Yay!")
else:
	print(":(")


### FIXED CODE ###

xs = [int(input()) for i in range(5)]
k = int(input())
if (xs[4] - xs[0] <= k):
	print("Yay!")
else:
	print(":(")
a, b, c = map(int, input().split())
A, B, C = map(int, input().split())
print("YES" if a==C and b==B and c==A else "NO")

### FIXED CODE ###

c1 = input()
c2 = input()
print("YES" if c1 == c2[::-1] else "NO")
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N-1):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
    if score[j[1]] < score[j[0]] + j[2]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

### FIXED CODE ###

N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-2:
      t = score[N-1]
    if i == N-1:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')
import itertools

n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)

color_range = list(range(c))
res = float('inf')
for x,y,z in itertools.permutations(color_range):
    cnt = 0
    for i in range(len(mod0)):
        cnt += D[mod0[i]][x]
    for i in range(len(mod1)):
        cnt += D[mod1[i]][y]
    for i in range(len(mod2)):
        cnt += D[mod2[i]][z]
    res = min(cnt, res)
print(res)

### FIXED CODE ###

import itertools
n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)

conv_0, conv_1, conv_2 = [],[],[]
for i in range(c):
    tmp0, tmp1, tmp2 = 0,0,0
    for j in range(len(mod0)):
        tmp0 += D[mod0[j]][i]
    for j in range(len(mod1)):
        tmp1 += D[mod1[j]][i]
    for j in range(len(mod2)):
        tmp2 += D[mod2[j]][i]
    conv_0.append(tmp0)
    conv_1.append(tmp1)
    conv_2.append(tmp2)
res = float('inf')
color_range = list(range(c))
for x,y,z in itertools.permutations(color_range, 3):
    cnt = 0
    cnt = conv_0[x] + conv_1[y] + conv_2[z]
    res = min(cnt, res)
print(res)
from functools import reduce
from math import gcd

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x.sort()
diff = []
for i in range(N):
    diff.append(x[i+1] - x[i])

print(reduce(gcd, diff))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x.sort()
diff = []
for i in range(N):
    diff.append(x[i+1] - x[i])

print(reduce(gcd, diff))
# 読み込み
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(list(map(str, input().rstrip())))

# 外枠を「.」で囲う準備
li = []
for i in range(H+2):
    li.append(["."]*(W+2))

# 外枠付きSの生成
for i in range(1, H+1):
    li[i][1:-1] = S[i-1]

# カウント用配列の準備
ans = []
for i in range(H+2):
    ans.append([0]*(W+2))
ans = np.array(ans)

# カウント処理
for h in range(1, H+1):
    for w in range(1, W+1):
        if li[h][w]=="#":
            ans[h-1:h+2, w-1:w+2] += 1

# カウント結果から必要な場所だけ切り出す
ans = ans.astype("str")
ans = ans[1:-1, 1:-1]

# 「#」で上書きしながら出力
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            ans[h, w] = "#"
    print("".join(ans[h]))

### FIXED CODE ###

import numpy as np

# 読み込み
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(list(map(str, input().rstrip())))

# 外枠を「.」で囲う準備
li = []
for i in range(H+2):
    li.append(["."]*(W+2))

# 外枠付きSの生成
for i in range(1, H+1):
    li[i][1:-1] = S[i-1]

# カウント用配列の準備
ans = []
for i in range(H+2):
    ans.append([0]*(W+2))
ans = np.array(ans)

# カウント処理
for h in range(1, H+1):
    for w in range(1, W+1):
        if li[h][w]=="#":
            ans[h-1:h+2, w-1:w+2] += 1

# カウント結果から必要な場所だけ切り出す
ans = ans.astype("str")
ans = ans[1:-1, 1:-1]

# 「#」で上書きしながら出力
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            ans[h, w] = "#"
    print("".join(ans[h]))
import math

A,B = map(float, input().split())
print(math.floor(A*B))


### FIXED CODE ###

import math
a,b = map(str, input().split())
b = b.replace(".","")
a = int(a)
b = int(b)
print(a * b // 100)
nnn = int(input())

a = [-2 for i in range(nnn)]
a[0] = 0

def m():
	return map(int,input().split())


def oon(x,n,nn,k):
	global a
	for i in range(len(x[n])):
		if x[n][i][0] != nn and a[nn] != -2:
			p = (k + x[n][i][1]) % 2
			if p == 0:
				a[x[n][i][0]] = 0
			else:
				a[x[n][i][0]] = 1
			oon(x,x[n][i][0],n,p)
		else:
			continue



b = [[] for i in range(nnn)]

for i in range(nnn-1):
	z,x,c = m();
	b[z-1].append([x-1,c])
	b[x-1].append([z-1,c])

oon(b,0,0,0)

for i in range(nnn):
	print(a[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
nnn = int(input())

a = [-2 for i in range(nnn)]
a[0] = 0

def m():
	return map(int,input().split())


def oon(x,n,nn,k):
	global a
	for i in range(len(x[n])):
		if x[n][i][0] != nn and a[nn] != -2:
			p = (k + x[n][i][1]) % 2
			if p == 0:
				a[x[n][i][0]] = 0
			else:
				a[x[n][i][0]] = 1
			oon(x,x[n][i][0],n,p)



b = [[] for i in range(nnn)]

for i in range(nnn-1):
	z,x,c = m();
	b[z-1].append([x-1,c])
	b[x-1].append([z-1,c])

oon(b,0,0,0)

for i in range(nnn):
	print(a[i])