← 返回题目列表

AtCoder · ttpc2019_c

C. 异或填充

中文机器翻译题面 查看原题

配点 : 100 点

背景

rian 在公园 我选取了一系列 N 整数。 瑞安决定将这个数字序列赠送给他的朋友纳里。

但是,仔细一看,rian 收藏的数列中有一些元素已经模糊得看不清了。 于是,rian 想起 nari 喜欢整数 X 于是对每个模糊的元素 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

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