#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 200100
using namespace std;
int n,m,now;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
class Link_Cut_Tree{
	struct node{int y,next;}e[MAXN<<1];
	int len,Link[MAXN],f[MAXN],rev[MAXN],st[MAXN],size[MAXN],Vsize[MAXN],son[MAXN][2];
	private:
		inline bool get(int x){return son[f[x]][1]==x;}
		inline bool isroot(int x){return son[f[x]][0]!=x&&son[f[x]][1]!=x;}
		inline void insert(int x,int y){
			e[++len].next=Link[x];Link[x]=len;e[len].y=y;
			e[++len].next=Link[y];Link[y]=len;e[len].y=x;	
		}
		inline void updata(int x){
			size[x]=Vsize[x]+1;
			if(son[x][0]) size[x]+=size[son[x][0]];
			if(son[x][1]) size[x]+=size[son[x][1]];	
		}
		inline void rotate(int x){
			int y=f[x],z=f[y],which=get(x);
			if(!isroot(y)) son[z][son[z][1]==y]=x;
			son[y][which]=son[x][which^1];  f[son[y][which]]=y;
			son[x][which^1]=y;  f[y]=x;  f[x]=z;
			updata(y);  updata(x);
		}
		inline void pushdown(int x){
			if(rev[x]){
				swap(son[x][0],son[x][1]);
				rev[son[x][0]]^=1;  rev[son[x][1]]^=1;
				rev[x]=0;
			}
		}
		inline void splay(int x){
			int top(0);  st[++top]=x;
			for(int i=x;!isroot(i);i=f[i]) st[++top]=f[i];
			for(int i=top;i;--i) pushdown(st[i]);
			for(int y=f[x];!isroot(x);rotate(x),y=f[x])
				if(!isroot(y)) rotate(get(x)==get(y)?y:x);
		}
		inline void access(int x){
			int last=0;
			while(x){
				splay(x);
				if(son[x][1]) Vsize[x]+=size[son[x][1]];
				if(last) Vsize[x]-=size[last];
				son[x][1]=last;  updata(x);
				last=x;  x=f[x];
			}
		}
		inline void reverse(int x){
			access(x); splay(x); rev[x]^=1;
		}
		inline void linkk(int x,int y){
			int root=find(x);
			access(x); splay(x);  f[y]=x;
			Vsize[x]+=size[y];  updata(x);
			access(y); splay(root);  int root_size=size[root];
			int temp=son[root][1];
			while(son[temp][0]) temp=son[temp][0];
			access(temp);  splay(temp);
			if((Vsize[temp]+1)*2>root_size||((Vsize[temp]+1)*2==root_size&&temp<root))
				now^=root,now^=temp,reverse(temp);
		}
		inline void dfs(int x,int fa){
			son[x][0]=son[x][1]=f[x]=rev[x]=Vsize[x]=0; size[x]=1;
			linkk(fa,x);
			for(int i=Link[x];i;i=e[i].next)
				if(e[i].y!=fa) dfs(e[i].y,x);
		}
	public:
		inline void pre(){
			for(int i=1;i<=n;++i) size[i]=1;
			for(int i=1;i<=n;++i) now^=i;
		}
		inline int find(int x){
			access(x); splay(x);
			while(son[x][0]) x=son[x][0];
			splay(x);
			return x;
		}
		inline void merge(int x,int y){
			if(size[find(x)]<size[find(y)])  swap(x,y);
			now^=find(y);
			dfs(y,x);
			insert(x,y);
		}
}Tree;
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  Tree.pre();
	for(int i=1;i<=m;++i){
		char opt[5]; scanf("%s",opt); 
		if(opt[0]=='A'){
			int x=read(),y=read();
			Tree.merge(x,y);
		}
		else if(opt[0]=='Q') printf("%d\n",Tree.find(read()));
		else printf("%d\n",now);
	}
	return 0;
}