Description

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.

Input Format

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 Format

Output $T$ lines, one for each test case.

For each test case, if it is possible, output RP; otherwise output ++.

3
5
01110
10010
5
11000
01100
5
00101
10100

RP
++
RP

Hint

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

For all test cases, $1\le n\le 10^5$ and $\sum n\le 2^{20}$.

Translated by ChatGPT 5