← 返回题目列表

Codeforces · 1163/E

E. 魔法排列

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

Kuro 刚刚了解了排列,他非常高兴能够创建一种新的排列类型。他选择了 $$$n$$$ 个不同的正整数,并将它们全部放入集合 $$$S$$$ 中。现在他定义了一个神奇的排列是:

- 从 $$$0$$$ 到 $$$2^x - 1$$$ 的整数排列,其中 $$$x$$$ 是非负整数。
- 排列中任意两个连续元素的按位异或是 $$$S$$$ 中的元素。

由于 Kuro 对魔法排列非常感兴趣,他想创造尽可能长的魔法排列。换句话说,他想要找到最大的非负整数$$$x$$$,这样就存在从$$$0$$$到$$$2^x - 1$$$的神奇整数排列。由于他是该主题的新手,他希望您帮助他找到 $$$x$$$ 的值以及 $$$x$$$ 的神奇排列。

输入

第一行包含整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 集合 $$$S$$$ 中的元素数量。

下一行包含 $$$n$$$ 不同的整数 $$$S_1, S_2, \ldots, S_n$$$ ($$$1 \leq S_i \leq 2 \cdot 10^5$$$) — 集合 $$$S$$$ 中的元素。

输出

在第一行中打印最大的非负整数 $$$x$$$,这样就存在从 $$$0$$$ 到 $$$2^x - 1$$$ 的神奇整数排列。

然后打印 $$$2^x$$$ 整数,描述从 $$$0$$$ 到 $$$2^x - 1$$$ 的神奇整数排列。如果有多个这样的神奇排列,请打印其中任何一个。

示例

输入 #1

3
1 2 3

输出 #1

2
0 1 3 2

输入 #2

2
2 3

输出 #2

2
0 2 1 3

输入 #3

4
1 2 3 4

输出 #3

3
0 1 3 2 6 7 5 4

输入#4

2
2 4

输出#4

0
0

输入 #5

1
20

输出 #5

0
0

输入 #6

1
1

输出 #6

1
0 1

注意

在第一个示例中,$$$0, 1, 3, 2$$$ 是一个神奇的排列,因为:

- $$$0 \oplus 1 = 1 \in S$$$
- $$$1 \oplus 3 = 2 \in S$$$
- $$$3 \oplus 2 = 1 \in S$$$

其中 $$$\oplus$$$ 表示按位异或运算。