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$$$ 表示按位异或运算。