CF251D Two Sets

小朋友 Petya 非常喜欢数字。最近他的妈妈送给了他一组 $n$ 个非负整数。唯一比数字更让 Petya 喜欢的是和小 Masha 玩耍。他立刻决定把他的这组数字分一部分给 Masha。为了让游戏更有趣，Petya 决定把一些数送给 Masha，使得下列条件满足： - 设 $x_{1}$ 表示 Petya 剩下所有数字的 $xor$ （按位异或）结果，$x_{2}$ 表示 Petya 送给 Masha 所有数字的 $xor$ 结果，使得 $x_{1}+x_{2}$ 尽可能大。 - 如果有多种分法都能使上述条件成立，Petya 希望 $x_{1}$ 尽量小。 其中 $xor$ 运算是按位异或操作，在 Pascal 语言中用 $xor$ 表示，在 C/C++/Java 语言中用 $^$ 表示。 请你帮 Petya 按照上述要求将这组数字分给自己和 Masha。如果有多种方案，输出任意一种。请注意，将一些数字全部给 Masha 或 Petya 也是允许的，这种情况下空集合的 $xor$ 视为 $0$。

第一行为整数 $n$（$1 \leq n \leq 10^{5}$），表示 Petya 收到的数字个数。 第二行包含 $n$ 个用空格隔开的数字。所有数字均为整数、非负且不超过 $10^{18}$。

输出 $n$ 个空格分隔的整数，第 $i$ 个数字为 $1$ 表示 Petya 保留输入中第 $i$ 个数字，为 $2$ 表示 Petya 把这个数字送给 Masha。按照输入顺序输出。

由 ChatGPT 5 翻译