Background

Legend has it that a long time ago, the little monster Nexus committed many evil deeds, so the great mage sealed it into the night sky. To complete the seal, the great mage cast spells to rearrange the stars, making the night sky show a specific constellation.

It is said that this seal has lasted to this day, and no one knows what it fully looked like in the past.

Problem Description

When reading ancient books, Little H discovered that the stars in the night sky can be abstracted as a sequence of non-negative integers. The star sequence in ancient times was $A = [a_1, \dots, a_n]$, and the sequence observed today is $B = [b_1, \dots, b_m]$.

The ancient book also records two kinds of spells used by the great mage when rearranging the stars. Specifically, for a current star sequence of length at least $2$, the great mage may cast one of the following two spells:

1. Delete the leftmost two elements of the sequence, and insert their XOR sum at the rightmost end.
2. Delete the rightmost two elements of the sequence, and insert their XOR sum at the leftmost end.

It can be seen that each time a spell is cast, the length of the star sequence decreases by exactly $1$. Little H suspects that perhaps the great mage used only these two spells back then, casting exactly $n - m$ times, turning the original sequence $A$ into the current sequence $B$. You need to help him determine whether this is possible; if it is possible, you also need to find a specific sequence of spells.

Input Format

This problem contains multiple test cases.

The first line of the input contains two non-negative integers $c, t$, representing the subtask ID and the number of test cases, respectively. $c = 0$ indicates that this subtask is the sample.

Then the test cases follow. For each test case:

• The first line contains two positive integers $n, m$.
• The second line contains $n$ non-negative integers $a_1, \dots, a_n$.
• The third line contains $m$ non-negative integers $b_1, \dots, b_m$.

Output Format

For each test case:

• Output a string Yes or No in the first line, indicating whether it is possible that the great mage transformed sequence $A$ into sequence $B$ using only these two spells.
• If possible, output $n - m$ positive integers from $\{1, 2\}$ in the second line, indicating the type of spell cast each time.

You can get partial credit by answering the first part correctly. For detailed scoring rules, see 【Scoring】.

0 5
2 2
1 2
1 2
3 2
3 4 2
6 3
5 3
2 3 4 5 6
6 1 1
6 1
1 2 3 4 5 6
0
7 2
3 3 5 6 1 2 8
11 3

Yes

Yes
2
Yes
1 1
No
Yes
2 1 2 1 1

Hint

【Sample 1 Explanation】

This sample contains five test cases in total.

For the first test case, sequences $A$ and $B$ are the same, so no spell needs to be cast.

For the second test case, after casting one spell of type $2$, the rightmost $4$ and $2$ of sequence $A$ are deleted, and $4 \operatorname{xor} 2 = 6$ is inserted at the leftmost end, obtaining sequence $B$.

For the third test case:

• After casting one spell of type $1$, the leftmost $2$ and $3$ of sequence $A$ are deleted, and $2 \operatorname{xor} 3 = 1$ is inserted at the rightmost end, obtaining the sequence $[4, 5, 6, 1]$.
• After casting another spell of type $1$, the leftmost $4$ and $5$ are deleted, and $4 \operatorname{xor} 5 = 1$ is inserted at the rightmost end, obtaining sequence $B$.

For the fourth test case, it can be proven that using only these two spells cannot transform sequence $A$ into sequence $B$.

【Sample 2】

See night/night2.in and night/night2.ans under the contestant directory.

This sample satisfies the constraints of subtasks $1, 2$.

【Sample 3】

See night/night3.in and night/night3.ans under the contestant directory.

This sample satisfies the constraints of subtask $4$.

【Sample 4】

See night/night4.in and night/night4.ans under the contestant directory.

This sample satisfies the constraints of subtasks $7 \sim 9$.

【Sample 5】

See night/night5.in and night/night5.ans under the contestant directory.

This sample satisfies the constraints of subtasks $12 \sim 14$.

【Constraints】

For all testdata:

• $1 \le t \le 10^3$;
• $1 \le m \le n \le 250$;
• For all $1 \le i \le n$, $0 \le a_i < 2^{30}$;
• For all $1 \le i \le m$, $0 \le b_i < 2^{30}$.

::cute-table{tuack}

A sequence $S = [s_1, \dots, s_k]$ is defined to be bizarre if and only if $k \ge 3$, and $s_1 = s_2 = s_3 = 1$, and for all $4 \le i \le k$, $2 \mid s_i$.

The cyclic shift of a sequence $S = [s_1, \dots, s_k]$ is defined as follows: for a positive integer $p$ ($1 \le p \le k$), the sequence $[s_p, s_{p+1}, \dots, s_k, s_1, \dots, s_{p-1}]$ is a cyclic shift of $S$.

• Special Property A: $3 \mid n$.
• Special Property B: sequences $A, B$ are both bizarre.
• Special Property C: each of sequences $A$ and $B$ has a cyclic shift that is bizarre.
• Special Property D: $2m \ge n$.

【Scoring】

This problem contains two parts. For each subtask:

• Part 1: For each test case in this subtask, if you correctly determine feasibility, you will get $50\%$ of the score for this subtask.
• Part 2: Based on that, if for each test case with answer Yes you can also correctly output a valid sequence of spells, you will get the remaining $50\%$ of the score for this subtask.

Note: For test cases with answer Yes, regardless of whether the contestant attempts to output a correct sequence of spells, you must output $n - m$ positive integers from $\{1, 2\}$ in the second line to satisfy the output format.

【Hint】

A checker.cpp is provided in the problem directory to check the validity of the spell sequence. Note: the provided checker.cpp only checks the correctness of the spell sequence for test cases whose answer is Yes, and does not check whether your feasibility judgment is correct.

Contestants can compile it into an executable in the problem directory using the following command:

g++ checker.cpp -o checker -std=gnu++14 -O2 -static

After compilation, contestants can test in the problem directory using the following command:

./checker <input_file> <output_file>

Here, <input_file> and <output_file> are the paths of the input file and the output file, respectively.

Note: The input file provided by the contestant must satisfy the input format and constraints given in the problem statement, and the output file must satisfy the given output format. Otherwise, the checking result is not guaranteed to be correct, and unexpected errors may occur.

Translated by ChatGPT 5