/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) および非負整数 K が与えられます．
以下の操作を 10^4 回以下行うことで A_1=K にすることが可能かどうか判定してください．
- 整数 i\ (1\leq i\leq N-1) を選ぶ．x=A_i\oplus A_{i+1} としたとき，A_i,A_{i+1} をそれぞれ x で置き換える．
ここで，\oplus はビット単位 \mathrm{XOR} 演算です．
可能な場合，そのような操作手順を一つ出力してください．
T 個のテストケースが与えられるので，それぞれについて答えてください．
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1\leq T\leq 50
- 3\leq N\leq 60
- 0\leq A_i,K\lt 2^{60}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる．
N K A_1 A_2 \ldots A_N
出力
\mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T に対する答えを順に以下の形式で出力せよ．
操作を 10^4 回以下行うことで A_1=K とすることが不可能な場合 No と出力せよ．
可能な場合，操作手順を以下の形式で出力せよ．
Yes M i_1 i_2 \ldots i_M
ここで， M は操作回数，i_j\ (1\leq j\leq M) は j 回目の操作で選ぶ整数 i を表す．0\leq M\leq 10^4, 1\leq i_j\leq N-1 を満たす必要がある．
条件を満たす操作手順が複数存在する場合，そのどれを出力しても正解とみなされる．
入力例 1
5 3 5 2 3 4 3 0 2 3 4 3 8 2 3 4 3 2 2 3 4 4 10 2 3 4 8
出力例 1
Yes 2 2 1 Yes 3 1 1 1 No Yes 0 Yes 4 2 3 2 1
1 つ目のテストケースについて，次のように操作をすることで A_1=5 とすることができます．
- i=2 を選ぶ．A=(2,7,7) になる．
- i=1 を選ぶ．A=(5,5,7) になる．
2 つ目のテストケースについて，次のように操作をすることで A_1=0 とすることができます．
- i=1 を選ぶ．A=(1,1,4) になる．
- i=1 を選ぶ．A=(0,0,4) になる．
- i=1 を選ぶ．A=(0,0,4) になる．
3 つ目のテストケースについて，10^4 回以下の操作によって A_1=8 とすることはできません．
Score : 800 points
Problem Statement
You are given a sequence of non-negative integers of length N: A=(A_1,A_2,\ldots,A_N) and a non-negative integer K.
Determine whether it is possible to make A_1=K by performing the following operation at most 10^4 times:
- Choose an integer i\ (1\leq i\leq N-1). Let x=A_i\oplus A_{i+1}, then replace both A_i,A_{i+1} with x.
Here, \oplus denotes the bitwise XOR operation.
If possible, output one such sequence of operations.
You are given T test cases, so solve each of them.
What is bitwise XOR operation?
The bitwise XOR of non-negative integers A, B, denoted A \oplus B, is defined as follows:
- When A \oplus B is written in binary, the digit in the 2^k (k \geq 0) place is 1 if exactly one of A, B has 1 in the 2^k place when written in binary, and 0 otherwise.
Constraints
- 1\leq T\leq 50
- 3\leq N\leq 60
- 0\leq A_i,K\lt 2^{60}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N K A_1 A_2 \ldots A_N
Output
Output your solutions for \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T in order in the following format:
If it is impossible to make A_1=K by performing the operation at most 10^4 times, output No.
If possible, output the sequence of operations in the following format:
Yes M i_1 i_2 \ldots i_M
Here, M is the number of operations, and i_j\ (1\leq j\leq M) represents the integer i chosen in the j-th operation. You need to satisfy 0\leq M\leq 10^4, 1\leq i_j\leq N-1.
If there are multiple sequences of operations that satisfy the conditions, any of them will be considered correct.
Sample Input 1
5 3 5 2 3 4 3 0 2 3 4 3 8 2 3 4 3 2 2 3 4 4 10 2 3 4 8
Sample Output 1
Yes 2 2 1 Yes 3 1 1 1 No Yes 0 Yes 4 2 3 2 1
For the first test case, you can make A_1=5 by performing the operations as follows:
- Choose i=2. A becomes (2,7,7).
- Choose i=1. A becomes (5,5,7).
For the second test case, you can make A_1=0 by performing the operations as follows:
- Choose i=1. A becomes (1,1,4).
- Choose i=1. A becomes (0,0,4).
- Choose i=1. A becomes (0,0,4).
For the third test case, it is impossible to make A_1=8 with at most 10^4 operations.