問題文

長さ $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}$
• 与えられる入力はすべて整数です。

入力

入力は以下の形式で標準入力から与えられます。

$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