P9082 - Beautiful Sequence

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：5 通过：4

Students from Antarctic Penguin Language School are studying sequence.

We call a sequence

A=(A1,A2,…,An)A=(A_1, A_2, \dots, A_n)

of length

n

beautiful when all the following conditions are true:

$A1≤A2≤⋯≤AnA_1 \le A_2 \le \dots \le A_n$
For each $A_i$ ( $1≤i≤n1\le i\le n$ ), $0≤Ai<2300\le A_i<2^{30}$ .
For each $1≤i<n1\le i<n$ , $Ai⊕Ai+1=BiA_i\oplus A_{i+1}=B_i$ , where $B$ is a given sequence, and $⊕\oplus$ represents bitwise XOR.

You need to find the

k

-th smallest lexicographically legal beautiful sequence

A

Each test contains multiple test cases. The first line contains the number of test cases

T

. The description of the test cases follows.
The first line contains two integers

n

k

(

1≤n≤1061\le n\le 10^6

1≤k≤2301\le k\le 2^{30}

).
The second line contains

n - 1

integers

B1,B2,…,Bn−1B_1, B_2, \dots, B_{n-1}

(

0≤Bi<2300\le B_i < 2^{30}

).
It is guaranteed that the sum of

n

over all test cases does not exceed

10^6

For each test case, output your operations in the following format.
If the number of beautiful sequences is less than

k

, output one line containing an integer

- 1

.
Otherwise, output one line containing

n

integers

A1,A2,…,AnA_1, A_2, \dots, A_n

separated by spaces --- the

k

-th smallest lexicographically legal beautiful sequence.

8 9 11
-1
0 0

9082: Beautiful Sequence