题目描述

在 X 星球上有 $n$ 个国家，每个国家占据着 X 星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。

X 星球上战乱频发，如果 A 国打败了 B 国，那么 B 国将永远从这个星球消失，而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治，会在 A 国和 B 国之间修建一条公路，即选择原 A 国的某个城市和 B 国某个城市，修建一条连接这两座城市的公路。

同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是 指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。 现在告诉你发生在 X 星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下 $3$ 种信息需要处理：

1. A x y：表示某两个国家发生战乱，战胜国选择了 $x$ 城市和 $y$ 城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
2. Q x：询问当前编号为 $x$ 的城市所在国家的首都。
3. Xor：询问当前所有国家首都编号的异或和。

输入格式

第一行是整数 $n,m$，表示城市数和需要处理的信息数。

接下来每行是一个信息，格式如题目描述（A、Q、Xor 中的某一种）。

输出格式

输出包含若干行，为处理 Q 和 Xor 信息的结果。

10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor

11
1
1
1
2
6
2

提示

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$。