問題文

長さ N の数列 a が与えられます。i 番目の要素は a_i です。

ニワンゴくんは a に対し、以下の操作を 0 回以上行うことができます。

• 操作：1 < i < N を満たす整数 i を選び、a_{i-1} を a_{i-1} \ {\rm{XOR}} \ a_{i} に、a_{i+1} を a_{i+1} \ {\rm{XOR}} \ a_{i} にそれぞれ置き換える。ここで {\rm{XOR}} はビットごとの排他的論理和の記号を表す。

0 回以上操作を行ったあとの a としてありうる数列のうち、辞書順最小のものを求めてください。

制約

• 1 \leq N \leq 10^5
• 0 \leq a_i \leq 10^{9}
• 与えられる入力は全て整数

入力例1

3
2 3 1

出力例1

1 3 2

• 1 回の操作により、(2,3,1) \rightarrow (2 \ \rm{XOR} \ 3, 3, 1 \ \rm{XOR} \ 3) = (1,3,2) と変化させることができます。

入力例2

5
1 1 3 2 1

出力例2

0 1 0 2 3

入力例3

15
454149310 980904516 263802120 650414794 570152508 496610001 940998475 895836185 33049807 966544922 733719158 536712208 292230877 949871052 342421559

出力例3

23988306 158687594 74711974 280079291 131007899 572247609 33049807 210457501 22094817 292230877 86347283 143004158 53812512 67781078 644469472