题目描述

现有 $N$ 个带电粒子，带正电子的粒子会和带负电子的粒子相互吸引，而带同一种电子的粒子会相互排斥。

有 $Q$ 次操作，每次操作表示为 $T_i,A_i,B_i$，可根据 $T_i$ 的不同分为三种类型：

• A 操作代表 $A_i,B_i$ 互相吸引。
• R 操作代表 $A_i,B_i$ 互相排斥。
• Q 操作询问按照目前已知的信息，如果 $A_i,B_i$ 放在一起，会发生什么。

对于每个 Q 操作，如果已经确定互相吸引，输出 A；如果已经确定互相排斥，输出 R；如果无法确定，输出 ?。

保证至少有一种可能使得所有操作不冲突。

输入格式

第一行两个整数 $N,Q$。

接下来的 $Q$ 行，每行一个字符 $T_i$ 与两个整数 $A_i,B_i$，表示一种操作。

输出格式

若干行，每行表示一次 Q 操作的回答。

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

提示

【样例 #1 解释】

对于第一次询问，并不能确定 $1,2$ 之间的关系，输出 ?。

对于第二次询问，可以确定 $1,2$ 相斥，输出 R。

【数据范围】

对于 $100\%$ 的数据：

• $1 \leq N,Q \leq 10^5$
• $1 \leq A_i \neq B_i \leq N$
• $T_i$ 仅可能为 A，R 或 Q。