F. Потерянный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Мои orz-дети, мы можем оптимизировать эту задачу с $$$O(S^3)$$$ до $$$O\left(T^\frac{5}{9}\right)$$$!
— Spyofgame, основатель религии Orz

Давным-давно Spyofgame изобрел известный массив $$$a$$$ (элементы которого нумеруются с $$$1$$$) длины $$$n$$$, который содержал знания о мире и о жизни. После этого он превратил его в матрицу $$$b$$$ (элементы которой нумеруются с $$$0$$$) размера $$$(n + 1) \times (n + 1)$$$, которая содержала знания о мире, о жизни, и о том, что за их пределами.

Spyofgame превратил $$$a$$$ в $$$b$$$ по следующим правилам.

  • $$$b_{i,0} = 0$$$ при $$$0 \leq i \leq n$$$;
  • $$$b_{0,i} = a_{i}$$$ при $$$1 \leq i \leq n$$$;
  • $$$b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}$$$ при $$$1 \leq i, j \leq n$$$.

Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

В наши дни археологи нашли знаменитую матрицу $$$b$$$. Однако многие ее элементы утеряны. Удалось прочесть лишь значения $$$b_{i,n}$$$ для всех $$$1 \leq i \leq n$$$ (обратите внимание, это некоторые элементы последнего столбца, а не строки).

Археологи хотят восстановить возможный массив $$$a$$$. Можете помочь им найти любой массив, который может быть массивом $$$a$$$?

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$b_{1,n}, b_{2,n}, \ldots, b_{n,n}$$$ ($$$0 \leq b_{i,n} < 2^{30}$$$).

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

Если какой-то массив $$$a$$$ подходит под данную информацию, выведите строку, содержащую $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Если существуют несколько решений, выведите любое из них.

Если решения не существует, выведите одно целое число $$$-1$$$.

Примеры
Входные данные
3
0 2 1
Выходные данные
1 2 3
Входные данные
1
199633
Выходные данные
199633
Входные данные
10
346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607
Выходные данные
725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365
Примечание

Если $$$a = [1,2,3]$$$, то $$$b$$$ будет следующей:

$$$\bf{0}$$$$$$\bf{1}$$$$$$\bf{2}$$$$$$\bf{3}$$$
$$$\bf{0}$$$$$$1$$$$$$3$$$$$$0$$$
$$$\bf{0}$$$$$$1$$$$$$2$$$$$$2$$$
$$$\bf{0}$$$$$$1$$$$$$3$$$$$$1$$$

Значения $$$b_{1,n}, b_{2,n}, \ldots, b_{n,n}$$$ равны $$$[0,2,1]$$$, что соответствует найденной археологами информации.