B. Восстановление И
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$b$$$ из $$$n - 1$$$ целого числа.

Массив $$$a$$$ из $$$n$$$ целых чисел называется хорошим, если $$$b_i = a_i \, \& \, a_{i + 1}$$$ для всех $$$1 \le i \le n-1$$$, где $$$\&$$$ обозначает операцию побитового И.

Постройте хороший массив или сообщите, что хороших массивов не существует.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$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$$$.

Если существует несколько решений, вы можете вывести любое из них.

Пример
Входные данные
4
2
1
3
2 0
4
1 2 3
5
3 5 4 2
Выходные данные
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]$$$.