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

#n=int(input())
n,k=map(int,input().split())
a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

l=[1]
for i in range(k):
    x=a[l[i]-1]
    if x in l:
        break
    else:
        l.append(x)

b=l.index(x)
c=len(l)-b
print(l[((k-b)%c)+b])


### FIXED CODE ###

#n=int(input())
n,k=map(int,input().split())
a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

l=[1]
s=set(l)
for i in range(k):
    x=a[l[i]-1]
    if x in s:
        break
    else:
        l.append(x)
        s.add(x)

b=l.index(x)
c=len(l)-b
print(l[((k-b)%c)+b])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


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
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


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
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

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

n,m,q = map(int,input().split())

table = []
res = []
for i in range(n+1):
    table.append([0]*(i+1))
    res.append([0]*(i+1))
for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1

for begin in range(1,n+1):
    s = 0
    for ending in range(begin,n+1):
        for k in range(begin,ending+1):
            s += table[ending][k]
        res[ending][begin] = s
for _ in range(q):
    start,end = map(int,input().split())
    print(res[end][start])


### FIXED CODE ###

n,m,q = map(int,input().split())

table = []
for i in range(n+1):
    table.append([0]*(n+1))
for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1

#2...n
for i in range(2,n+1):

    #1...n-1
    for j in range(1,n+2-i):
        table[i+j-1][j] += table[i+j-1][j+1]+table[i+j-2][j]-table[i+j-2][j+1]

for _ in range(q):
    start,end = map(int,input().split())
    print(table[end][start])
### BUGGY CODE ###

from operator import itemgetter
import sys

def main():
    n = int(input())
    keys = []
    for i in xrange(n):
        keys.append(map(int,raw_input().split())+[i])

    T = Tree()
    T.recursive_add_Node(keys,0)

    q = int(input())
    for i in xrange(q):
        sx, tx, sy, ty = map(int,raw_input().split())
        nums = []
        find(T.root,[sx,sy],[tx,ty],0,nums)
        nums.sort()
        for i in nums:
            sys.stdout.write("{}\n".format(i))
        print ("")

        

def find(z,s,t,d,nums):
    if(s[0]<=z.key[0]<=t[0])and(s[1]<=z.key[1]<=t[1]):
        nums.append(z.num)
    d += 1
    xy = d%2
    if (z.left != None)and(z.key[xy]>=s[xy]):
        find(z.left,s,t,d,nums)    
    if (z.right != None)and(z.key[xy]<=t[xy]):
        find(z.right,s,t,d,nums)


class Tree():
    def __init__(self):
        self.root = None

    def add_Node(self,k,n):
        y = None
        x = self.root
        d = 0
        xy = 0
        while(x != None):
            d += 1
            xy = d%2
            y = x
            if x.key[xy] > k[xy]:
                x = x.left
            else:
                x = x.right
        
        z = Node(k,n)
        z.parent = y
        z.depth  = d

        if y == None:
            self.root = z
        elif y.key[xy] > k[xy]:
            y.left = z
        else:
            y.right = z
        
    def recursive_add_Node(self,keys,depth):
        keys.sort(key=itemgetter(depth%2))
        id_mean = len(keys)/2
        self.add_Node(keys[id_mean][:2],keys[id_mean][2])
       
        if id_mean != 0:
            self.recursive_add_Node(keys[:id_mean],depth+1)
        if id_mean+1 != len(keys):
            self.recursive_add_Node(keys[id_mean+1:],depth+1)

class Node():
    def __init__(self,k,n):
        self.key    = k
        self.num    = n
        self.depth  = None
        self.parent = None
        self.left   = None
        self.right  = None
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

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

import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
d.sort(reverse = True)
for i in range(k):
    if d[0][-1] > 0:
        a.pop(a.index(d[0][-1]))
        d[0][-1] -= 1
        a.insert(bisect.bisect_right(a, d[0][-1]) ,d[0][-1])
        d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
        d.sort(reverse = True)
    else:
        break
print(d[0][0])

### FIXED CODE ###

def main():

    import numpy as np
    
    n, k = map(int, input().split())
    a = np.array(input().split(), np.int64)
    f = np.array(input().split(), np.int64)
    a.sort()
    a = a[::-1]
    f.sort()
    right = np.max(a*f)
    left = 0
    while right > left:
        middle = (right + left)//2
        b = 0
        
        if np.sum(np.maximum(a-middle//f, 0)) <= k:
            right = middle
        else:
            left = middle+1

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

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

A_accumulate_cost = [0]
lastCost = 0
for i in range(N):
    lastCost += A[i]
    A_accumulate_cost.append(lastCost)

B_accumulate_cost = [0]
lastCost = 0
for i in range(M):
    lastCost += B[i]
    B_accumulate_cost.append(lastCost)

max_num = 0
for i in range(N+1):
    A_cost = A_accumulate_cost[i]
    if (A_cost > K):
        break

    for j in range(M, -1, -1):
        if (A_cost + B_accumulate_cost[j] <= K):
            if (i + j > max_num):
                max_num = i+j
            break

print(max_num)

### FIXED CODE ###

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

A_accumulate_cost = [0]
lastCost = 0
for i in range(N):
    lastCost += A[i]
    A_accumulate_cost.append(lastCost)

B_accumulate_cost = [0]
lastCost = 0
for i in range(M):
    lastCost += B[i]
    B_accumulate_cost.append(lastCost)

max_num = 0
p = M
for i in range(N+1):
    A_cost = A_accumulate_cost[i]
    if A_cost > K:
        break

    for j in range(p, -1, -1):
        if A_cost + B_accumulate_cost[j] <= K:
            p = j
            if i + j > max_num:
                max_num = i+j
            break

print(max_num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt, vEn):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if vNow == vEn: break
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, wt in adjList[vNow]:
            c2 = cNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs


N, M = map(int, input().split())
edges = []
v0s = [[] for _ in range(N)]
v2s = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    edges.append((u, v))
    v0s[v].append(u)
    v2s[u].append(v)

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

adjL0 = [set() for _ in range(N)]
for u, v in edges:
    for v0 in v0s[u]:
        for v2 in v2s[v]:
            adjL0[v0].add((v2, 1))

adjL = [[] for _ in range(N)]
for v, adj in enumerate(adjL0):
    adjL[v] = list(adj)

costs = Dijkstra(adjL, S, T)

if costs[T] == INF:
    print(-1)
else:
    print(costs[T])


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

INF = float('inf')

def bfsMinCosts(adjList, vSt):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = 0
    Q = deque([vSt])
    while Q:
        vNow = Q.popleft()
        cNow = costs[vNow]
        for v2 in adjList[vNow]:
            if costs[v2] == INF:
                costs[v2] = cNow + 1
                Q.append(v2)
    return costs

N, M = map(int, input().split())
adjL = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    adjL[3*u+0].append(3*v+1)
    adjL[3*u+1].append(3*v+2)
    adjL[3*u+2].append(3*v+0)

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

costs = bfsMinCosts(adjL, 3*S+0)

if costs[3*T+0] == INF:
    print(-1)
else:
    print(costs[3*T+0]//3)
### BUGGY CODE ###

from math import log2,floor
N = int(input())
A = list(map(int,input().split()))
L = max([len(bin(x)) for x in A])
bits = [0]*L
for x in A:
    for i in range(L):
        if (x>>i)&1:
            bits[i] += 1
mod = 10**9+7
ans = 0
for i in range(L):
    b = bits[i]
    ans = (ans+b*(N-b)*(2**i))%mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

a = int(input())
l = list(map(int, input().split()))
ans = 1
for i in range(a):
  ans = ans * l[i]
if 10**18 < ans:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

a = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 1
for i in range(a):
  ans = ans * l[i]
  if 10**18 < ans:
    ans = -1
    break

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

n = int(input())
l = list(map(int, input().split()))
ans = 0

for i in range(0, 10**5+1):
  count = 0
  for j in l:
    if j == i or j == i+1 or j == i-1:
      count += 1
  if count > ans:
    ans = count

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0
count = {}
for i in range(0, 10**5+1):
  count[i] = 0

for i in l:
  count[i] = count[i] + 1

for i in range(0, 10**5+1):
  if i == 0:
    temp = count[i] + count[i+1]
  elif i == 10**5:
    temp = count[i] + count[i-1]
  else:
    temp = count[i] + count[i+1] + count[i-1]

  if temp > ans:
    ans = temp

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

n, *p_n = map(int, open(0).read().split())

count = 0
for i in range(n):
    if min(p_n[:i+1]) == p_n[i]:
        count += 1
print(count)

### FIXED CODE ###

n, *p_n = map(int, open(0).read().split())

count = 0
p_n_min = p_n[0]
for i in range(n):
    p_n_min = min(p_n_min,p_n[i])
    if p_n_min == p_n[i]:
        count += 1
print(count)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

l1=sorted([i+j for i in a for j in b],reverse=True)[:k]
l2=sorted([i+j for i in l1 for j in c],reverse=True)[:k]
for i in l2:
  print(i)


### FIXED CODE ###

import sys
input=sys.stdin.readline
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
l1=sorted([i+j for i in a for j in b],reverse=True)[:k]
l2=sorted([i+j for i in l1 for j in c],reverse=True)[:k]
for i in l2:
  print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')

h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)  


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)
### BUGGY CODE ###

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

mi_A=min(A)

count=0
bad=0
for j in range(N-1,-1,-1):
  if A[j]%mi_A==0:
    count=count+1
  elif bad==1:
    break
  else:
    bad=bad+1
if count>=N-1:
  ans=mi_A
  
else:
  for i in range(mi_A//2+1,0,-1):
    if mi_A%i==0:
      count=0
      bad=0
      for j in range(N-1,-1,-1):
        if A[j]%i==0:
          count=count+1
        elif bad==1:
          break
        else:
          bad=bad+1
      if count>=N-1:
        ans=i
        break


A.remove(min(A))
if len(A)==N-1:
  mi_A=min(A)
  count=0
  bad=0
  for j in range(0,N-1):
    if A[j]%mi_A==0:
      count=count+1
    else:
      break
  if count>=N-1:
    ans=mi_A
    
  else:
    for i in range(mi_A//2+1,0,-1):
      if mi_A%i==0:
   
        count=0
        bad=0
        for j in range(0,N-1):
        
          if A[j]%i==0:
            count=count+1
         
          else:
        
            break
        if (count>=N-1) and (i>ans):
          ans=i
          break
  
print(ans)

### FIXED CODE ###

def gcd(a,b):
  if a==b:
    return a 
  elif a<b:
    a,b=b,a
    while a%b!=0:
      a,b=b,a%b
    return b
  else:
    while a%b!=0:
      a,b=b,a%b
    return b
 

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

data_ans=[]
data1=[A[0]]
data2=[A[N-1]]
l=A[0]
m=A[N-1]
for i in range(1,N-2):
  l=gcd(l,A[i])
  m=gcd(m,A[N-i-1])
  data1.append(l)
  data2.append(m)
l=gcd(l,A[N-2])
m=gcd(m,A[1])
data_ans.append(l)
data_ans.append(m)
for i in range(0,N-2):
  data_ans.append(gcd(data1[i],data2[N-3-i]))
print(max(data_ans))
### BUGGY CODE ###

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

ans = 0

for i in range(0,N-1):
    for j in range(i+1, N):
        product = (A[i] * A[j])
        #print(product)
        ans += product
print(ans%(10**9 + 7))

### FIXED CODE ###

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

S = sum(A)
S_2 = sum(map(lambda x: x*x, A))

ans = (S*S - S_2)//2 #切り捨て除算にしないと結果をfloatで返してきやがるので

print(ans%(10**9 + 7))
### BUGGY CODE ###

import itertools

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    for x in range(N):
        tmp = tuple([y for idx, y in enumerate(A) if idx != x])
        result = tuple(filter(lambda t: t[0] == t[1], itertools.combinations(tmp, 2)))
        print(len(result))


### FIXED CODE ###

import sys
import itertools
from collections import Counter
sys.setrecursionlimit(10**8)
if __name__ == "__main__":
    N = int(input())
    A = input().split()
    counter = Counter(A)
    result = 0
    for c in counter.values():
        result += c*(c-1)//2
    for a in A:
        k = counter[a]
        print(result - k*(k-1)//2 + (k-1)*(k-2)//2)
### BUGGY CODE ###

S = input()

N = len(S)
dp = [[0 for _ in range(13)] for _ in range(10 ** 5 + 1)]
mod = 10 ** 9 + 7
dp[0][0] = 1

for i in range(N):
    s = S[i]
    for j in range(10):
        if s != "?" and s != str(j):
            continue
        for r in range(13):
            dp[i+1][(r * 10 + j) % 13] += dp[i][r]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[N][5])


### FIXED CODE ###

S = input()

mod = 10 ** 9 + 7
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(10 ** 5 + 5)]
dp[0][0] = 1

for i in range(N):
    c = 0
    if S[i] == "?":
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i+1][(k * 10 + j) % 13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[N][5])
### BUGGY CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)

### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

N = int(input())
L = [[int(x) for x in input().split()] for _ in range(N-1)]

dic = {}
for i in range(N-1):
    if L[i][0] in dic:
        dic[L[i][0]].append([L[i][1], L[i][2]])
    else:
        dic[L[i][0]] = [[L[i][1], L[i][2]]]
    if L[i][1] in dic:
        dic[L[i][1]].append([L[i][0], L[i][2]])
    else:
        dic[L[i][1]] = [[L[i][0], L[i][2]]]

ans_list = ["0"]*(N+1)
q = [[1, 0]]
visited = []
while len(q) > 0:
    t = q.pop(0)
    v = t[0]
    d = t[1]
    for i in range(len(dic[v])):
        if dic[v][i][0] not in visited:
            q.append([dic[v][i][0], d+dic[v][i][1]])
            visited.append(dic[v][i][0])
            if (d+dic[v][i][1])%2 == 1:
                ans_list[dic[v][i][0]] = "1"
                
for i in range(1, N+1):
    print(ans_list[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])
    
d = [0]*(N)

q = deque()
q.append([0, 0])
visited = [0]*(N)
while q:
    temp = q.pop()
    for L in edge[temp[0]]:
        if visited[L[0]] == 0:
            d[L[0]] = L[1] + temp[1]
            q.append([L[0], d[L[0]]])
            visited[L[0]] = 1
            
for i in range(N):
    print(d[i]%2)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    S = [0] + list(map(int, input().split()))
    T = [0] + list(map(int, input().split()))

    dp = [[0] * (M+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i] == T[j]:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            dp[i][j] %= MOD

    return (dp[N][M] + 1) % MOD


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    S = [0] + list(map(int, input().split()))
    T = [0] + list(map(int, input().split()))

    dp = [[0] * (M+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i] == T[j]:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            dp[i][j] %= MOD

    return (dp[N][M] + 1) % MOD


if __name__ == '__main__':
    print(main())