Problem Description

There are $N$ charged particles. Particles with positive charges attract particles with negative charges, while particles with the same type of charge repel each other.

There are $Q$ operations, each represented by $T_i, A_i, B_i$, which can be divided into three types based on $T_i$:
- A operation means $A_i$ and $B_i$ attract each other.
- R operation means $A_i$ and $B_i$ repel each other.
- Q operation queries what would happen if $A_i$ and $B_i$ were placed together based on the current information.

For each Q operation, if they attract each other, output A; if they repel each other, output R; if it is indeterminable, output ?.

It is guaranteed that there is at least one scenario where all operations are consistent.

Input Format

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

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

Output Format

Several lines, each representing the answer to a Q operation.

Sample Input and Output

Input Sample #1

2 3
Q 1 2
R 1 2
Q 1 2

Output Sample #1

?
R

Input Sample #2

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

Output Sample #2

A
A

Notes

Sample #1 Explanation

For the first query, the relationship between $1$ and $2$ is indeterminable, so output ?.

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

Data Range

For $100\%$ of the data:
- $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.

见题面 Input 部分

见题面 Output 部分