首都

题目描述

在X星球上有N个国家,每个国家占据着X星球的一座城市。由于国家之间是敌对关系,所以不同国家的两个城市是不会有公路相连的。 X星球上战乱频发,如果A国打败了B国,那么B国将永远从这个星球消失,而B国的国土也将归A国管辖。A国国王为了加强统治,会在A国和B国之间修建一条公路,即选择原A国的某个城市和B国某个城市,修建一条连接这两座城市的公路。 同样为了便于统治自己的国家,国家的首都会选在某个使得其他城市到它距离之和最小的城市,这里的距离是指需要经过公路的条数,如果有多个这样的城市,编号最小的将成为首都。 现在告诉你发生在X星球的战事,需要你处理一些关于国家首都的信息,具体地,有如下3种信息需要处理: - `A x y`:表示某两个国家发生战乱,战胜国选择了x城市和y城市,在它们之间修建公路(保证其中城市一个在战胜国另一个在战败国)。 - `Q x`:询问当前编号为x的城市所在国家的首都。 - `Xor`:询问当前所有国家首都编号的异或和。

输入输出格式

输入格式


第一行是整数N,M,表示城市数和需要处理的信息数。 接下来每行是一个信息,格式如题目描述(A、Q、Xor中的某一种)。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

11 
1 
1 
1 
2 
6 
2 

说明

对于100%的数据,2<=N<=100000,1<=M<=200000。