P7338 "MdOI R4" Color

Student M has a grid paper with $2$ rows and $n$ columns. At the beginning, all cells are white. She decides to color some cells. Specifically, each time she chooses two **adjacent (4-connected, i.e., sharing a common edge) white** cells, colors one of them red, and the other blue. Her goal is to make some specified cells become red through **any number of operations**, with **no requirements on the other cells**. Please help her determine whether the goal can be achieved using the operations above.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. Then there are $T$ test cases, each consisting of three lines: - The first line contains a positive integer $n$, the number of columns of the grid paper. - The second line contains a 01 string $p_{1\ldots n}$, where $p_i=1$ means the cell in row $1$, column $i$ must be red; otherwise there is no requirement. - The third line contains a 01 string $q_{1\ldots n}$, where $q_i=1$ means the cell in row $2$, column $i$ must be red; otherwise there is no requirement.

Output $T$ lines, one for each test case. For each test case, if it is possible, output `RP`; otherwise output `++`.

[Sample Explanation]  In the figure above, the left side shows one possible solution for the first test case, and the right side shows one possible solution for the third test case. For the second test case, there is no solution that satisfies the requirements. [Constraints and Notes] **This problem uses bundled tests.** |Subtask ID|$n\le$|Special Property|$T\le$|Score| |:-|:-|:-|:-|:-| |$1$|$3$|No special restrictions|$10$|$10$| |$2$|$10$|No special restrictions|$10$|$20$| |$3$|No special restrictions|All $1$ are in the same row|$10$|$1$| |$4$|No special restrictions|The number of $1$ does not exceed $4$|$10$|$13$| |$5$|$10^3$|No special restrictions|$10$|$25$| |$6$|No special restrictions|No special restrictions|$10$|$30$| |$7$|$16$|No special restrictions|$65536$|$1$| For all test cases, $1\le n\le 10^5$ and $\sum n\le 2^{20}$. Translated by ChatGPT 5