← 返回题目列表

Codeforces · 251/D

D. 两套

中文机器翻译题面 查看原题

小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