Problem Description

Given a sequence of length $N$ consisting of non-negative integers $A_1, A_2, \ldots, A_N$, create a program that, for each $k = 1, 2, \ldots, N$, outputs the value of

• $X = A_1 \text{ xor } A_2 \text{ xor } \ldots \text{ xor } A_k$ and then
• $(A_1 \text{ xor } X) + (A_2 \text{ xor } X) + \ldots + (A_k \text{ xor } X)$.

Note that the definition of $X$ changes with $k$.

The xor of integers $c_1, c_2, \ldots, c_m$ is defined as follows:

• Let $X$ be the xor value.
• When $X$ is expressed in binary, the value of the $2^k$ (where $k$ is a non-negative integer) digit is $1$ if there are an odd number of $c_1, c_2, \ldots, c_m$ whose binary representation has $1$ at the $2^k$ digit, and $0$ if there are an even number.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer for each $k = 1, 2, \ldots, N$ on a new line.

Sample Input and Output

Sample Input #1

3
7 5 3

Sample Output #1

0
12
12

Sample Input #2

7
12 42 61 31 34 53 17

Sample Output #2

0
54
110
138
142
233
252

Notes/Hints

Constraints

• $1 \le N \le 3 \times 10^5$
• $0 \le A_i$
• All given inputs are integers.

Sample Explanation 1

• For $k = 1$, $X = 7$, so $A_1 \text{ xor } X = 0$.
• For $k = 2$, $X = 7 \text{ xor } 5 = 2$, so $A_1 \text{ xor } X = 5$ and $A_2 \text{ xor } X = 7$, resulting in a total value of $12$.
• For $k = 3$, $X = 7 \text{ xor } 5 \text{ xor } 3 = 1$, so $A_1 \text{ xor } X = 6$, $A_2 \text{ xor } X = 4$, and $A_3 \text{ xor } X = 2$, resulting in a total value of $12$.

见题面 Input 部分

见题面 Output 部分