Pinely Round 4 (Div. 1 + Div. 2) |
---|
Закончено |
Вам дан массив $$$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$$$.
Если существует несколько решений, вы можете вывести любое из них.
42132 041 2 353 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]$$$.
Название |
---|