P15651 [NOI Qualifier Joint Contest 2026] Night Sky

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.

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.

**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$.

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】.

### 【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} | Subtask ID | $n \le$ | $m \le$ | $T \le$ | Special Property | |:-:|:-:|:-:|:-:|:-:| | $1,2$ | $16$ | $16$ | $10^3$ | None | | $3$ | $250$ | $1$ | $30$ | ^ | | $4$ | ^ | $2$ | ^ | ^ | | $5,6$ | ^ | ^ | ^ | A | | $7 \sim 9$ | $50$ | $50$ | $50$ | B | | $10,11$ | $250$ | $250$ | $30$ | ^ | | $12 \sim 14$ | $50$ | $50$ | $50$ | C | | $15,16$ | $250$ | $250$ | $30$ | ^ | | $17 \sim 19$ | $50$ | $50$ | $50$ | D | | $20,21$ | $250$ | $250$ | $30$ | ^ | | $22,23$ | $50$ | $50$ | $50$ | None | | $24,25$ | $250$ | $250$ | $30$ | ^ | 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 ``` Here, `` and `` 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