Charged Particles Interaction

You are given N charged particles. Particles with opposite charges attract each other and particles with the same charge repel each other.

There are Q operations. Each operation is represented as $T_i, A_i, B_i$, where $T_i$ can be one of three types:

• A: Indicates that particles $A_i$ and $B_i$ attract (i.e. they have opposite charges).
• R: Indicates that particles $A_i$ and $B_i$ repel (i.e. they have the same charge).
• Q: A query asking, given the current information, what would happen if particles $A_i$ and $B_i$ are placed together.

For each query operation, output A if they will attract, R if they will repel, and ? if it is impossible to determine.

It is guaranteed that there exists at least one possible assignment of charges that does not conflict with all the operations.

The relations can be modeled with a union-find data structure with parity. Two particles are in the same set if their relationship is determined; the parity indicates if their charges are the same (repel) or different (attract).

Note: All formulas above must be written in LaTeX format. For example, the charge condition should be: $A_i$ and $B_i$ attract if $parity[A_i] \oplus parity[B_i] = 1$, and repel if $\oplus$ equals $0$.

inputFormat

The first line contains two integers N and Q, the number of particles and the number of operations, respectively.

Each of the next Q lines contains an operation in the format:

T A B

where T is one of A, R, or Q, and A and B are the indices of the particles (1-indexed).

outputFormat

For each query operation (where T is Q), print one line containing the result: A if particles attract, R if they repel, or ? if it is uncertain.

sample

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

A
A