AtCoder Regular Contest 021

B - Your Numbers are XORed...


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

小学 N 年生になったばかりの妹は、授業で 排他的論理和 というものについて学びました。

排他的論理和とは、例えば非負整数 PQ の排他的論理和を R としたとき、以下のように定義されます。

  • R2 進数表記したときの 2^k (0 ≦ kk は整数) の位の値は、P2 進数表記したときの 2^k の位の値を pQ2 進数表記したときの 2^k の位の値を q としたとき、p=q なら 0pq なら 1 となります。

具体的には、35 の排他的論理和の値は、32 進数表記が 01152 進数表記が 101 のため、2 進数表記が 110 となる 6 が排他的論理和の値となります。

排他的論理和の素晴らしさを知った妹は、嬉しさの余り、周囲にあった非負整数の値を手当たり次第に排他的論理和された値に書き換えました。

ところが、その中には兄が提出する予定の書類が入っていたのです!

兄は外出中なので、今のうちに元の数列に復元することにしました。手がかりとして、以下のことが分かっています。

  • 書類には L 個の非負整数 A_1A_2,…,A_L が書いてありました。これらの数は今や書類には書き残されていません。妹の目的は、これらの数を知ることです。
  • 書類には L 個の非負整数 B_1B_2,…,B_L が書いてあります。これらの数は書類に書き残されているので知ることができます。

B_1B_2,…,B_L は、以下の定義で表される数です。

  • 1 ≦ i ≦ L-1 を満たす整数 i に関して、B_i の値は A_iA_{i+1} を排他的論理和した値に等しい。
  • B_L の値は A_LA_1 を排他的論理和した値に等しい。

大変残念なことに場合によっては該当する元の数列が存在しないことや、複数通り存在する場合があります。どうしましょう!

困った妹は、今日の占いのラッキーアイテムが辞書であったことを思い出しました。辞書、じしょ、辞書順…

最終的に、以下のルールを追加することにしました。

  • 該当する元の数列が存在しない場合は、仕方がないので存在しないむねを示す -1 を答えとします。
  • 該当する元の数列が複数存在する場合は、辞書順最小な数列を出力します。

ここで、2 つの数列 S_1S_2,…,S_LT_1T_2,…,T_L に関して、 S_1S_2,…,S_LT_1T_2,…,T_L より辞書順で小さいというのは、以下の条件を満たす場合とします。

  • ある整数 i (1 ≦ i ≦ L) に関して、1 ≦ j ≦ i-1 を満たすどの整数 j に関しても S_j=T_j が成立し、かつ S_i<T_i が成立する。

あなたは妹の代わりに上記の条件を満たす数列を出力するプログラムを作成してください。


入力

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

L
B_1
B_2
:
B_L
  • 1 行目には、書類に書かれている数字の個数を表す整数 L (2 ≦ L ≦ 10^5) が与えられる。
  • 2 行目から L 行では、書類に残されている非負整数について書かれている。このうち i 行目では整数 B_i (0 ≦ B_i < 2^{31}) が与えられる。

出力

元の非負整数列 A_1A_2,…,A_L として考えられるものが存在する場合は、それらのうち辞書順最小なものを L 行にわたって出力せよ。このうち i 行目には整数 A_i を出力せよ。存在しない場合は -1 を出力せよ。出力の末尾にも改行を入れること。


入力例1

2
1
1

出力例1

0
1

A_1A_2 を排他的論理和した値が 1 となるものが正解になります。このような 2 つの数は複数通りありますが,A_1=0A_2=1 を満たす場合が辞書順最小になります。


入力例2

3
1
4
1

出力例2

-1

条件を満たす元の数列は存在しません。きっとどこかで誤った操作をしたのでしょう。


入力例3

3
1
2
3

出力例3

0
1
3

Submit提出する