2604. 黑白树的操作

【题目描述】

不要紧张。题目的名字只是一个MD5。

小A有一堆小圆点。某天，他无聊了，于是他想把这些点连成一棵无根树。

小A觉得他不能放过这个防AK的好机会，于是他想借此考考你。

一开始，小A有n个点，这n个点分别编号为1~n。每个点都有颜色，任何时刻，点的颜色都只能是黑白两种颜色之一。初始时，所有点都是白色的。

小A一共会进行m次操作，每次操作只可能是以下的三种之一：

A u v w：添加一条连接(u,v)的无向边，长度为w。

C u：反转点u的颜色，即如果点u原来是白色则反转后会变成黑色，反之亦然。

Q u：询问所有与点u连通的黑点到点u的距离之和。定义连通的两点间的距离为两点间简单路径上的边长度之和。

因为小A觉得这个问题太简单了，所以他决定强制在线。

【输入格式】

第一行一个整数T，表示测试点编号。

第二行两个整数n,m，分别表示点的个数和操作数。

以下m行，每行描述一个操作，格式如上所述。

为了防止你采用各种离线算法水掉本题，本题强制在线，每次输入的整数均需异或(上一次询问的答案mod n)。如果还没有进行询问，那么上一次询问的答案是0。

注意，mod n是在n的剩余系下，比如-1 mod 5 = 4.

【样例输入】

3 7

A 1 2 3

C 1

Q 2

Q 3

A 2 3 1

C 2

Q 3

【样例输出】

3

0

5

【样例解释】

样例输入解密后为

3 7

A 1 2 3

C 1

Q 2

Q 3

A 2 3 1

C 2

Q 3

【数据范围与约定】

本题共有20个测试点，每个测试点的数据范围和特殊性质如下：

你可以假定给出的所有操作均合法，即进行A操作后一定不会产生环，给出的点的编号都在1~n之内。但请注意，数据不保证最后得到的一定是一棵树(也即所有点可能不连通)。