← 返回题目列表

Codeforces · 571/D

D. 校园

中文机器翻译题面 查看原题

奥斯科尔科沃市有一个校园,由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)的学生人数变为零。