Background

Translated from NOISG2019 Prelim C.Experimental Charges。

Problem Description

There are $N$ charged particles. A particle with a positive electron charge will attract a particle with a negative electron charge, while particles with the same electron charge will repel each other.

There are $Q$ operations. Each operation is given as $T_i, A_i, B_i$, and can be one of three types depending on $T_i$:

• Operation A means $A_i$ and $B_i$ attract each other.
• Operation R means $A_i$ and $B_i$ repel each other.
• Operation Q asks, based on the information known so far, what would happen if $A_i$ and $B_i$ are placed together.

For each Q operation, if they attract each other, output A; if they repel each other, output R; if it cannot be determined, output ?.

It is guaranteed that there is at least one possibility such that all operations are consistent.

Input Format

The first line contains two integers $N, Q$.

The next $Q$ lines each contain a character $T_i$ and two integers $A_i, B_i$, describing an operation.

Output Format

Output several lines, each line being the answer to one Q operation.

2 3
Q 1 2
R 1 2
Q 1 2

?
R

4 5
R 1 2
A 2 3
A 1 4
Q 2 4
Q 1 3

A
A

Hint

Sample #1 Explanation

For the first query, the relationship between $1$ and $2$ cannot be determined, so output ?.

For the second query, it can be determined that $1$ and $2$ repel each other, so output R.

Constraints

For $100\%$ of the testdata:

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_i \neq B_i \leq N$
• $T_i$ can only be A, R, or Q。

Translated by ChatGPT 5