小Petya非常喜欢数字。最近,他的母亲给了他一个 n 个非负整数的集合。除了数字之外,佩蒂亚只喜欢一件事:和小玛莎一起玩。他立即决定将自己新收藏的一部分送给她。为了让游戏变得更加有趣,Petya 决定为 Masha 提供满足以下条件的数字集合:
- 让我们引入 x1 来表示 Petya 剩下的所有数字的异或;让我们引入 x2 来表示他给玛莎的所有数字的异或。值 (x1 + x2) 必须尽可能大。
- 如果有多种方法来划分集合以便满足前面的条件,则 Petya 最小化值 x1。
异或运算是按位排除“OR”,在 Pascal 语言中表示为“xor”,在 C/C++/Java 中表示为“^”。
帮助 Petya 按上述方式划分集合。如果有多种合适的划分方法,请找出其中任何一种。请注意,Petya 将部分号码交给 Masha 后,他可能就没有号码了。相反的情况也是可能的,彼佳什么也不给玛莎。在这两种情况下,我们必须假设一组空数字的异或等于 0。
输入
第一行包含整数 n (1 ≤ n ≤ 105),显示 Petya 的母亲给了他多少个数字。第二行包含实际的空格分隔的数字。它们都是整数、非负且不超过 1018。
输出
打印 n 个以空格分隔的整数,如果 Petya 在其集合中保留第 i 个后面的数字,则其中第 i 个整数应等于 1;如果 Petya 将相应的数字提供给 Masha,则第 i 个整数应等于 2。这些数字按照它们在输入中给出的顺序进行索引。
示例
输入 #1
6 1 2 3 4 5 6
输出 #1
2 2 2 2 2 2
输入 #2
3 1000000000000 1000000000000 1000000000000
输出 #2
2 2 2
输入 #3
8 1 1 2 2 3 3 4 4
输出 #3
1 2 1 2 2 2 1 2