奥斯科尔科沃市有一个校园,由n个学生宿舍、n个大学和n个军事办公室组成。最初,第i个宿舍属于第i个大学,分配给第i个军部。
生活还在继续,校园也在不断发生着一些变化。变化可以有四种类型:
1. aj大学与bj大学合并。之后bj大学的宿舍全部分配给aj大学,bj大学消失。
2.军事办公室cj与军事办公室dj合并。之后,所有分配给军事办公室dj的宿舍都分配给军事办公室cj,军事办公室dj消失。
3、xj大学学生入住宿舍。设kxj是学生入住时属于该大学的宿舍数量。那么xj大学每个宿舍的学生人数增加kxj(注意,属于该大学的宿舍越多,该大学每个宿舍入住的学生就越多)。
4. yj 号军事办公室对分配给它的所有宿舍进行突击搜查,并带走那里的所有学生。
因此,在每个时刻,每个宿舍都被分配给一所大学和一个军事办公室。最初,所有宿舍都是空的。
你的任务是处理校园内发生的变化并回答有关目前宿舍qj 有多少人居住的问题。
输入
第一行包含两个整数,n和m(1≤n,m≤5·105)——分别是宿舍数和查询数。
接下来的 m 行包含查询,每行都以以下格式之一给出:
- «U aj bj» — 合并大学;
- «M cj dj» — 合并军事办公室;
- «A xj» — xj大学的学生搬进宿舍;
- «Z yj» — 对军事办公室 yj 的一次突袭;
- «Q qj» — 询问宿舍 qj 的人数的查询。
输出
在第 i 行中打印第 i 个询问宿舍人数的查询的答案。
示例
输入 #1
2 7 A 1 Q 1 U 1 2 A 1 Z 1 Q 1 Q 2
输出 #1
1 0 2
输入 #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
2 1 1 0 1
注意
考虑第一个样本测试:
- 在第一次查询大学1时只拥有宿舍1,因此查询宿舍1后将有1名学生。
- 第三次查询大学1后拥有宿舍1和2。
- 第四个查询将属于 1 号大学的宿舍 1 和 2 的学生人数加 2。之后,第一个宿舍有 3 个学生,第二个宿舍有 2 个学生。
- 在第五次查询时,居住在宿舍 1(分配给军事办公室 1)的学生人数变为零。