← 返回题目列表

AtCoder · arc021_2

B. 你的数字已异或...

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

問題文

小学 N 我刚上一年级的妹妹正在上课。 我了解到了一种叫做 排他的論理和 的东西。

异或例如是一个非负整数 P 和 我讨厌 Q 的异或 R 定义如下。

  • R 除以 2 当表示为基数时 2^k (0 ≦ k,k 是一个整数),位值为P 除以 2 当表示为基数时 2^k 位值 当 p、Q 除以 2 当表示为基数时 2^k 位值 当 q 时,p=q 如果 0、p≠q 如果 1 。

具体来说,3 和 我讨厌 5 的异或值为3 的 2 基数表示法是 011、5 的 2 基数表示法是 101 因为2 基数表示法是 110 变为 6 是异或值。

我的妹妹,了解到了异或的奇妙之处,非常高兴,她用异或值随机重写了她周围的非负整数的值。

然而,里面是我哥哥预定提交的一份文件!

由于我哥哥出城了,我决定现在恢复原来的号码顺序。作为线索,我们知道以下几点:

  • 该文档有 已写入 L 非负整数 A_1,A_2,…,A_L 。这些数字现在还没有写下来。姐姐的目的就是要知道这些数字。 写入
  • 该文档有 已写入 L 非负整数 B_1,B_2,…,B_L 。您可以知道这些数字,因为它们记录在文档中。

B_1,B_2,…,B_L 是由以下定义表示的数字。 关于

  • 1 ≦ i ≦ L-1 的整数只有 i ,B_i 的值为 等于 A_i 和 我讨厌 A_{i+1} 的异或。
  • B_L 的值为 等于 A_L 和 我讨厌 A_1 的异或。

不幸的是,在某些情况下,对应的原始数字序列可能不存在,或者可能存在多个版本。我们该怎么办!

烦恼的妹妹记得今天算命的幸运物是一本字典。字典,字典,字典顺序……

最后,我决定添加以下规则。

  • 如果对应的原始数列不存在,我们只能表明它不存在。 让 -1 作为答案。
  • 如果有多个对应的原始数列,则按字典顺序输出最小的数列。

在这里,2 数字序列 如果满足以下条件,则按字典顺序,值小于 S_1,S_2,…,S_L 和 我讨厌 T_1,T_2,…,T_L , S_1,S_2,…,S_L 是 这将是第 T_1,T_2,…,T_L :

  • 一些整数 关于 i (1 ≦ i ≦ L), 哪个整数满足1 ≦ j ≦ i-1 关于 j 关于 S_j=T_j 成立,并且 S_i<T_i 成立。

请代表你姐姐创建一个程序,输出满足上述条件的数列。


入力

输入是按以下格式从标准输入给出的。

L
B_1
B_2
:
B_L
  • 1 行包含一个整数,表示文档上写入的数字数量。 L (2 ≦ L ≦ 10^5) 。
  • 2 在 L 行描述了文档中剩余的非负整数。其中 i 行是一个整数 B_i (0 ≦ B_i < 2^{31}) 。

出力

原始非负整数序列 如果存在可能的 A_1,A_2,…,A_L ,请选择其中字典顺序最小的一个。 输出超过 L 线。其中 输出 i 行是一个整数 A_i 。如果它不存在 输出 -1 。还在输出末尾添加换行符。 通过异或运算


入力例1

2
1
1

出力例1

0
1

A_1 和 我讨厌 A_2 得到的值为 正确答案是 1 。像这样 2 有多个号码, 满足A_1=0,A_2=1 的情况是字典顺序最小值。


入力例2

3
1
4
1

出力例2

-1

没有满足条件的原始数列。我一定是在某个地方犯了错误。


入力例3

3
1
2
3

出力例3

0
1
3