很久以前,Spyofgame 发明了著名的数组 $$$a$$$($$$1$$$ 索引),长度为 $$$n$$$,其中包含有关世界和生活的信息。之后,他决定将其转换为大小为 $$$(n + 1) \times (n + 1)$$$ 的矩阵 $$$b$$$ ($$$0$$$-索引),其中包含有关世界、生活和其他方面的信息。
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$$$。然而,矩阵的许多元素已经丢失。他们只知道 $$$1 \leq i \leq n$$$ 的 $$$b_{i,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$$$。
示例
输入 #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
注意
如果我们让 $$$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]$$$,这与考古学家的发现一致。