CF1713F.Lost Array

My orzlers, we can optimize this problem from $O(S^3)$ to $O\left(T^\frac{5}{9}\right)$!

— Spyofgame, founder of Orzlim religion

A long time ago, Spyofgame invented the famous array $a$ ($1$-indexed) of length $n$ that contains information about the world and life. After that, he decided to convert it into the matrix $b$ ($0$-indexed) of size $(n + 1) \times (n + 1)$ which contains information about the world, life and beyond.

Spyofgame converted $a$ into $b$ with the following rules.

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

Here $\oplus$ denotes the bitwise XOR operation.

Today, archaeologists have discovered the famous matrix $b$. However, many elements of the matrix has been lost. They only know the values of $b_{i,n}$ for $1 \leq i \leq n$ (note that these are some elements of the last column, not the last row).

The archaeologists want to know what a possible array of $a$ is. Can you help them reconstruct any array that could be $a$?

我的orz信徒们，我们可以将该问题的复杂度从 $O(S^3)$ 优化至 $O\left(T^\frac{5}{9}\right)$！

— Spyofgame，Orzlim 宗教创始人

很久以前，Spyofgame 发明了一个著名的长度为 $n$ 的数组 $a$（下标从 $1$ 开始），其中蕴含着关于世界与生命的全部信息。随后，他决定将其转换为一个大小为 $(n + 1) \times (n + 1)$ 的矩阵 $b$（下标从 $0$ 开始），其中蕴含着关于世界、生命乃至更深远领域的信息。

Spyofgame 按照如下规则将 $a$ 转换为 $b$：

• 若 $0 \leq i \leq n$，则 $b_{i,0} = 0$；
• 若 $1 \leq i \leq n$，则 $b_{0,i} = a_{i}$；
• 若 $1 \leq i, j \leq n$，则 $b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}$。

此处 $\oplus$ 表示 按位异或运算。

如今，考古学家们发现了这个著名的矩阵 $b$。然而，矩阵中许多元素已经遗失。他们仅知道 $b_{i,n}$ 的值（其中 $1 \leq i \leq n$）（注意：这些是最后一列中的某些元素，而非最后一行）。

考古学家们希望知道一个可能的数组 $a$ 是什么。你能帮他们重构出一个可能的 $a$ 吗？

The first line contains a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$).

The second line contains $n$ integers $b_{1,n}, b_{2,n}, \ldots, b_{n,n}$ ($0 \leq b_{i,n} \lt 2^{30}$).

第一行包含一个整数 $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} \lt 2^{30}$）。

If some array $a$ is consistent with the information, print a line containing $n$ integers $a_1, a_2, \ldots, a_n$. If there are multiple solutions, output any.

If such an array does not exist, output $-1$ instead.

如果存在某个数组 $a$ 满足给定信息，请输出一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 的结果。若存在多个解，输出任意一个即可。

若不存在满足条件的数组，则输出 $-1$。

If we let $a = [1,2,3]$, then $b$ will be:

$\bf{0}$

$\bf{1}$

$\bf{2}$

$\bf{3}$

$\bf{0}$

$1$

$3$

$0$

$\bf{0}$

$1$

$2$

$2$

$\bf{0}$

$1$

$3$

$1$

The values of $b_{1,n}, b_{2,n}, \ldots, b_{n,n}$ generated are $[0,2,1]$ which is consistent with what the archaeologists have discovered.

如果我们令 $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]$，这与考古学家的发现一致。