C - XOR Filling /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100

背景

rian ちゃんは公園で N 個の整数からなる数列を拾いました。 rian ちゃんはこの数列を、友達の nari くんにプレゼントすることにしました。

ところが、よく見たところ rian ちゃんの拾った数列はいくつかの要素がかすれて読めなくなっていました。 そこで、nari くんが整数 X が好きだということを思い出した rian ちゃんは、かすれた要素それぞれに 0 以上 X 以下の整数を入れ、N 個全ての要素の排他的論理和を取った値がちょうど X になるようにしてから、nari くんに数列をプレゼントすることにしました。 果たして rian ちゃんは nari くんに数列をプレゼントできるでしょうか...?

問題文

自然数 N, X と数列 (a_1, a_2, \ldots, a_N) が入力として与えられます。 ただし、いくつかの a_i は情報が欠損しています。また、欠損した a_i0 \leq a_i \leq X であることがわかっています。

a_1 \text{ XOR } a_2 \text{ XOR } \cdots \text{ XOR } a_N = X

を満たすような数列に復元してください。

XOR とは

整数 A, B のビットごとの排他的論理和 X は、以下のように定義されます。

  • X を二進表記した際の 2^kk \geq 0)の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 となります。

例えば、 3 \text{ XOR } 5 = 6 となります(二進数表記すると: 011 \text{ XOR } 101 = 110 )。

制約

  • 入力はすべて整数である。
  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq X \leq 10^9
  • -1 \leq a_i \leq 10^9
    a_i = -1 のときは、その情報が欠損していることを意味する。

入力

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

N X
a_1 a_2 \ldots a_N

出力

条件を満たす数列を 1 つ出力せよ。条件を満たす数列が存在しない場合は -1 を出力せよ。


入力例 1

4 11
8 -1 1 5

出力例 1

8 7 1 5

入力例 2

6 7
-1 2 -1 4 -1 6

出力例 2

1 2 3 4 5 6
  • このケースでは、これ以外にも条件を満たす数列が存在します。

入力例 3

1 2
3

出力例 3

-1