遗失的数组

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$、下标从 $1$ 开始的数组 $a$。按照下列规则构造下标从 $0$ 开始、大小为 $(n+1)\times(n+1)$ 的矩阵 $b$：

• 对所有 $0\le i\le n$，$b_{i,0}=0$；
• 对所有 $1\le i\le n$，$b_{0,i}=a_i$；
• 对所有 $1\le i,j\le n$，$b_{i,j}=b_{i,j-1}\oplus b_{i-1,j}$。

其中 $\oplus$ 表示按位异或。

现在给出 $b_{1,n},b_{2,n},\ldots,b_{n,n}$。请恢复一个与这些信息一致的数组 $a$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $b_{1,n},b_{2,n},\ldots,b_{n,n}$。

输出格式

若存在解，输出一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$；若不存在，输出 -1。

样例输入 1

3
0 2 1

样例输出 1

1 2 3

样例输入 2

1
199633

样例输出 2

199633

样例输入 3

10
346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607

样例输出 3

725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365

数据范围

$1\le n\le5\cdot10^5$，$0\le b_{i,n}<2^{30}$。

说明

对任意合法输入，满足条件的数组 $a$ 实际上存在且唯一。