问题描述

给定一个由长为 $N$ 的非负整数组成的序列 $A_1, A_2, \ldots, A_N$。对于每个 $k = 1, 2, \ldots, N$，请编写一个程序，满足以下要求：

• 令 $X = A_1$ ${\rm xor}$ $A_2$ ${\rm xor}$ $\ldots$ ${\rm xor}$ $A_k$，
• 输出 $(A_1$ ${\rm xor}$ $X) + (A_2$ ${\rm xor}$ $X) + \ldots + (A_k$ ${\rm xor}$ $X)$ 的值。

请注意，$X$ 的定义随着 $k$ 的变化而变化。

另外，整数 $c_1, c_2, \ldots, c_m$ 的 ${\rm xor}$ 定义如下：

• 设求得的 ${\rm xor}$ 值为 $X$，
• 如果当将 $X$ 表示为二进制时，$2^k$ ($k$ 是非负整数) 位的值为奇数个，则 $X$ 的二进制表示中的 $2^k$ 位的值为 $1$；如果为偶数个，则 $X$ 的二进制表示中的 $2^k$ 位的值为 $0$。

约束条件

• $1 \le N \le 3 \times 10^5$
• $0 \le A_i < 2^{30}$
• 所有输入都是整数。

输入

输入以以下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出

对于每个 $k = 1, 2, \ldots, N$，请每行输出一个答案。

输入示例 1

3
7 5 3

输出示例 1

0
12
12

• 当 $k = 1$ 时，$X = 7$，因此 $A_1$ ${\rm xor}$ $X = 0$。
• 当 $k = 2$ 时，$X = 7$ ${\rm xor}$ $5 = 2$，因此 $A_1$ ${\rm xor}$ $X = 5$，$A_{2}$ ${\rm xor}$ $X = 7$，总和为 $12$。
• 当 $k = 3$ 时，$X = 7$ ${\rm xor}$ $5$ ${\rm xor}$ $3 = 1$，因此 $A_1$ ${\rm xor}$ $X = 6$，$A_{2}$ ${\rm xor}$ $X = 4$，$A_{3}$ ${\rm xor}$ $X = 2$，总和为 $12$。

输入示例 2

7
12 42 61 31 34 53 17

输出示例 2

0
54
110
138
142
233
252