题目描述

有一个长度为 $n$ 的序列，初始全为 $0$。

有两类对下标的集合，初始时每一类各有 $n$ 个集合，编号为 $i$ 的集合里有下标 $i$。

一共有 $m$ 个操作，操作有五种：

1. U x y 将第一类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
2. M x y 将第二类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
3. A x 将第一类编号为 $x$ 的集合中的所有下标在序列中对应的数加上 $x$ 的集合大小。
4. Z x 将第二类编号为 $x$ 的集合中的所有下标在序列中对应的数设为 $0$。
5. Q x 询问序列中下标为 $x$ 的位置上的数。

$n,m \le 5 \times 10^5$。

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 5\times 10^{5}$。

接下来 $m$ 行，每行一个操作。

输出格式

对于每个询问，依次在一行中输出一个整数表示答案。

2 7
A 1
Q 1
U 1 2
A 1
Z 1
Q 1
Q 2

1
0
2

5 12
U 1 2
M 4 5
A 1
Q 1
A 3
A 4
Q 3
Q 4
Z 4
Q 4
A 5
Q 5

2
1
1
0
1