Time Limit: 2 sec / Memory Limit: 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_i が 0 \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^k (k \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