Two Sets

题意翻译

给你$N$ 个数$a_i$ ,要求把这些数分成两堆 使第一堆的异或和加第二堆的异或和最大 在满足这个条件下使第一堆的异或和最小,输出方案。 $N\le10^5,a_i\le10^{18}$ 感谢@Kelin 提供的翻译

题目描述

Little Petya likes numbers a lot. Recently his mother has presented him a collection of $ n $ non-negative integers. There's only one thing Petya likes more than numbers: playing with little Masha. He immediately decided to give a part of his new collection to her. To make the game even more interesting, Petya decided to give Masha such collection of numbers for which the following conditions fulfill: - Let's introduce $ x_{1} $ to denote the $ xor $ of all numbers Petya has got left; and let's introduce $ x_{2} $ to denote the $ xor $ of all numbers he gave to Masha. Value $ (x_{1}+x_{2}) $ must be as large as possible. - If there are multiple ways to divide the collection so that the previous condition fulfilled, then Petya minimizes the value $ x_{1} $ . The $ xor $ operation is a bitwise excluding "OR", that is denoted as "xor" in the Pascal language and "^" in C/C++/Java. Help Petya divide the collection as described above. If there are multiple suitable ways to divide it, find any of them. Please note that after Petya gives a part of his numbers to Masha, he may have no numbers left. The reverse situation is also possible, when Petya gives nothing to Masha. In both cases we must assume that the $ xor $ of an empty set of numbers equals 0.

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=10^{5} $ ), showing how many numbers Petya's mother gave him. The second line contains the actual space-separated numbers. They are all integer, non-negative and do not exceed $ 10^{18} $ .

输出格式

Print $ n $ space-separated integers, the $ i $ -th of them should equal either 1, if Petya keeps the number that follows $ i $ -th in his collection, or it should equal 2, if Petya gives the corresponding number to Masha. The numbers are indexed in the order in which they are given in the input.

输入输出样例

输入样例 #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