Мои 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\)?
Выходные данные
Если какой-то массив \(a\) подходит под данную информацию, выведите строку, содержащую \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Если существуют несколько решений, выведите любое из них.
Если решения не существует, выведите одно целое число \(-1\).
Примечание
Если \(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]\), что соответствует найденной археологами информации.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 2 1
|
1 2 3
|
|
2
|
1
199633
|
199633
|
|
3
|
10
346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607
|
725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365
|