問題文

長さ N の 0 以上の整数からなる数列 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 は 0 以上の整数) の位の値は、c_1, c_2, \ldots, c_m のうち、二進数表記したときの 2^k の位の値が 1 となるものが奇数個ならば 1、偶数個ならば 0 となる。

制約

• 1 \le N \le 3 \times 10^5
• 0 \le A_i < 2^{30}
• 与えられる入力はすべて整数です。

入力例 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