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

1. У меня карточка ai.
2. У человека номер bi карточка ci (bi ≠ i).

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

Входные данные

В первой строке расположено число n (2 ≤ n ≤ 1000). В следующих n строках находятся тройки чисел ai, bi, ci - показания друзей.

Выходные данные

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