← 返回题目列表

Codeforces · 1991/B

B. 和重建

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

给定一个数组 $$$b$$$,其中包含 $$$n - 1$$$ 整数。

如果 $$$b_i = a_i \, \& \, a_{i + 1}$$$ 对于 $$$1 \le i \le n-1$$$,则 $$$n$$$ 整数的数组 $$$a$$$ 被称为良好,其中 $$$\&$$$ 表示按位 AND 运算符。

构造一个好的数组,或者报告不存在好的数组。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n - 1$$$ 整数 $$$b_1, b_2, \ldots, b_{n - 1}$$$ ($$$0 \le b_i < 2^{30}$$$) — 数组 $$$b$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果不存在好的数组,则输出单个整数 $$$-1$$$。

否则,输出 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — 一个好的数组 $$$a$$$ 的元素。

如果有多个解,则可以输出其中任何一个。

示例

输入 #1

4
2
1
3
2 0
4
1 2 3
5
3 5 4 2

输出 #1

5 3
3 2 1
-1
3 7 5 6 3

注意

在第一个测试用例中,$$$b = [1]$$$。一个可能的好数组是 $$$a=[5, 3]$$$,因为 $$$a_1 \, \& \, a_2 = 5 \, \& \, 3 = 1 = b_1$$$。

在第二个测试用例中,$$$b = [2, 0]$$$。一个可能的好数组是 $$$a=[3, 2, 1]$$$,因为 $$$a_1 \, \& \, a_2 = 3 \, \& \, 2 = 2 = b_1$$$ 和 $$$a_2 \, \& \, a_3 = 2 \, \& \, 1 = 0 = b_2$$$。

在第三个测试用例中,$$$b = [1, 2, 3]$$$。可以看出不存在好的数组,因此输出为$$$-1$$$。

在第四个测试用例中,$$$b = [3, 5, 4, 2]$$$。一个可能的好数组是 $$$a=[3, 7, 5, 6, 3]$$$。