Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

inline char getc()

{

	register char c = getchar();

	while(!isalpha(c))c = getchar();

	while(isalpha(getchar()));

	return c;

}

int n,m;

#define MAXN 100010

struct node

{

	int c[2],fa;

	int sum,tot;

	bool rev;

}t[MAXN];

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void maintain(int rt){t[rt].sum = t[t[rt].c[0]].sum + t[t[rt].c[1]].sum + t[rt].tot + 1;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

void pushdown(int rt)

{

	if(t[rt].rev)

	{

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k)

{

	for(int i = 0;k;i = k,k = t[k].fa)

	{

		splay(k);

		t[k].tot += t[t[k].c[1]].sum;

		t[k].c[1] = i;

		t[k].tot -= t[t[k].c[1]].sum;

		maintain(k);

	}

	return;

}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void split(int x,int y){makeroot(x);access(y);splay(y);return;}

void link(int k,int f){split(k,f);t[k].fa = f;t[f].tot += t[k].sum;maintain(f);return;}

int cen[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int search(int rt)

{

	int lsum = 0,rsum = 0,half = t[rt].sum / 2,tag = t[rt].sum & 1,now = 2e9,ls,rs;

	while(rt)

	{

		pushdown(rt);

		ls = lsum + t[t[rt].c[0]].sum;rs = rsum + t[t[rt].c[1]].sum;

		if(ls <= half && rs <= half)

		{

			if(tag){now = rt;break;}

			else if(rt < now)now = rt;

		}

		if(ls < rs)lsum += t[t[rt].c[0]].sum + t[rt].tot + 1,rt = t[rt].c[1];

		else rsum += t[t[rt].c[1]].sum + t[rt].tot + 1,rt = t[rt].c[0];

	}

	return now;

}

int ans = 0;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		f[i] = i;cen[i] = i;

		ans ^= i;t[i].sum = 1;

	}

	char opt;

	int x,y;

	for(int i = 1;i <= m;++i)

	{

		opt = getc();

		if(opt == 'X')printf("%d\n",ans);

		if(opt == 'Q')

		{

			x = rd();

			printf("%d\n",cen[find(x)]);

		}

		if(opt == 'A')

		{

			x = rd();y = rd();

			int a = cen[find(x)],b = cen[find(y)];

			link(x,y);split(a,b);int cc = search(b);

			f[find(x)] = find(y);

			cen[find(y)] = cc;

			ans = ans ^ a ^ b ^ cc;

		}

	}

	return 0;

}