Тёмыч и N его друзей играют в игру. Тёмыч выходит из комнаты. На карточках пишутся числа от 1 до N, и каждый из друзей забирает себе по одной карточке так, чтобы Тёмыч не знал, у кого какая карточка. Будем считать, что друзья перенумерованы числами от 1 до N. После того, как Тёмыч возвращается, каждый из друзей произносит по 2 высказывания следующего вида (сформулированы для друга номер i):

1. У меня карточка a_i.
2. У человека номер b_i карточка c_i (b_i ≠ i).

Из каждых двух таких утверждений одно является истинным, а другое ложным. Известно, что никакие два человека не сказали, что у человека b карточка c, и ни один человек не сказал, что у человека b карточка c в случае, если человек b признался, что у него именно эта карточка. Задача Тёмыча — определить для каждого друга, какое из высказываний является истиной.

В первой строке расположено число N (2 ≤ N ≤ 1000). В следующих N строках находятся тройки чисел a_i, b_i, c_i — показания друзей.

Выведите через пробел N чисел — номер высказывания каждого из друзей (1 или 2), являющегося истиной. Гарантируется, что хотя бы одно решение существует.