#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <deque>

using namespace std;

#define pr pair <int,int>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define rep(i,j,k) for(int i = (j);i <= (k);i ++)
#define repd(i,j,k,d) for(int i = (j);i <= (k);i += (d))
#define rrep(i,j,k) for(int i = (j);i >= (k);i --)
#define rrepd(i,j,k,d) for(int i = (j);i >= (k);i -= (d))
#define mo 1000000009
#define cl(x,d) memset(x,(d),sizeof(x))
#define repg(i,u) for(int i = h[u];~i;i = n1[i])
typedef long long ll;

void read(int &x){
	char ch = getchar();	int f = 1;	while((ch != '-') && (ch < '0' || ch > '9'))	ch = getchar();
	if(ch == '-')	f = -1, x = 0;	else	 x = ch - 48;
	ch = getchar();	while(ch >= '0' && ch <= '9')	x = x * 10 + ch - 48, ch = getchar();	x *= f;
}
void read(ll &x){
	char ch = getchar();	int f = 1;	while((ch != '-') && (ch < '0' || ch > '9'))	ch = getchar();
	if(ch == '-')	f = -1, x = 0;	else	 x = ch - 48;
	ch = getchar();	while(ch >= '0' && ch <= '9')	x = x * 10LL + ch - 48, ch = getchar();	x *= f;
}
void _print(const int &x){	if(x < 10)	putchar(48 + x);	else	_print(x / 10), _print(x % 10);}
void _print(const ll &x){	if(x < 10)	putchar(48 + x);	else	_print(x / 10), _print(x % 10);}
void print(const int &x){	if(x < 0)	putchar('-'), _print(-x);	else	_print(x);}
void print(const ll &x){	if(x < 0)	putchar('-'), _print(-x);	else	_print(x);}
void println(const int &x){	print(x);	putchar('\n');}
void println(const ll &x){	print(x);	putchar('\n');}

const int R1 = 691504013, R2 = 308495997, trans = 276601605;
#define N 200010
int n;

//#define max(x,y) (((x)<(y))?(y):(x))
//#define min(x,y) (((x)<(y))?(x):(y))
int ql,qr;
int p[N * 2],n1[N * 2],h[N],ee=0,fa[N],fir[N],seq[N],top[N],rank[N],d[N],q[N],sz[N],stot = 0;

void ae(int x,int y){
	p[ee] = y;	n1[ee] = h[x];	h[x] = ee ++;
}
void pre(int x){
	int s = 0,e = 1; 
	q[1] = x;
	d[x] = 1;
	while(s < e){
		int u = q[++ s];
		repg(i,u){
			if(p[i] != fa[u]){
				d[p[i]] = d[u] + 1;
				fa[p[i]] = u;
				q[++ e] = p[i];
			}
		}
	}
	sz[0] = 0;
	rrep(i,e,1){
		int u = q[i],he = 0;
		sz[u] ++;
		repg(j,u){
			if(p[j] != fa[u]){
				sz[u] += sz[p[j]];
				if(sz[p[j]] > sz[he])	he = p[j];
			}
		}
		fir[u] = he;
  	}
	int now = 0,la = 0;
	rep(i,1,e){
		if(!rank[q[i]]){
			for(int j = q[i];j;j = fir[j])	seq[++ now] = j, rank[j] = now;
			rep(j,la + 1,now)	top[seq[j]] = seq[la + 1];
			la = now;
		}
	}
}
struct edge{
	int x,y;
}e[N];
int st[N],ed[N],anc[20][N],pos[N],pp[N];
void dfs(int u){ 
	seq[++ stot] = u;
	pp[u] = stot;
	st[u] = stot;
	repg(i,u)	dfs(p[i]);
	ed[u] = stot;
}
int lca(int x,int y){
	if(d[x] > d[y])	swap(x,y);
	int k = d[y] - d[x], j = 0;
	while(k){
		if(k & 1)	 y = anc[j][y];
		k >>= 1;
		j ++;
	}
	if(x == y)	return x;
	rrep(i,19,0)	if(anc[i][x] != anc[i][y])	x = anc[i][x], y = anc[i][y];
	return anc[0][x];
}
int rootA[N],rootB[N];
struct tree{
	struct node{
		int l,r,lh,rh,sum;
	}t[25000000];
	#define ls t[x].l
	#define rs t[x].r
	int R,_R[N],RS[N],rt[N * 20],tot,cur,curtot,S;
	void initR(int _r){
		cl(rt,0);
		cl(t,0);
		R = _r;
		cur = curtot = 0;
		tot = 0;
		_R[0] = 1;
		RS[0] = 0;
		rep(i,1,n){
			_R[i] = 1LL * _R[i - 1] * R % mo;
			RS[i] = RS[i - 1] + _R[i];
			if(RS[i] >= mo)	RS[i] -= mo;
		}
	}
	void modifyL(int &x,int p,int l,int r){
		t[x = ++tot] = t[p];
		if(ql <= l && r <= qr){
			t[x].sum = (1LL * S * _R[l - ql] % mo * RS[r - l + 1] + t[x].sum) % mo;
			t[x].lh = (1LL * S * _R[l - ql] + t[x].lh) % mo;
			return;
		}
		int mid = (l + r) >> 1;
		if(ql <= mid)	modifyL(ls,t[p].l,l,mid);
		if(mid < qr)	modifyL(rs,t[p].r,mid + 1,r);
		t[x].sum = (1LL * t[ls].sum + t[rs].sum + 1LL * (t[x].lh + t[x].rh) * RS[r - l + 1]) % mo;
	}
	void modifyR(int &x,int p,int l,int r){
		t[x = ++tot] = t[p];
		if(ql <= l && r <= qr){
			t[x].sum = (1LL * S * _R[qr - r] % mo * RS[r - l + 1] + t[x].sum) % mo;
			t[x].rh = (1LL * S * _R[qr - r] + t[x].rh) % mo;
			return;
		}
		int mid = (l + r) >> 1;
		if(ql <= mid)	modifyR(ls,t[p].l,l,mid);
		if(mid < qr)	modifyR(rs,t[p].r,mid + 1,r);
		t[x].sum = (1LL * t[ls].sum + t[rs].sum + 1LL * (t[x].lh + t[x].rh) * RS[r - l + 1]) % mo;
	}
	int ask(int l,int r,int x){
		if(!x || l > r)	return 0;
		if(ql <= l && r <= qr)	return t[x].sum;
		int mid = (l + r) >> 1, ret = 0;
		if(ql <= mid)	ret += ask(l,mid,ls);
		if(ret >= mo)	ret -= mo;
		if(mid < qr)	ret += ask(mid + 1,r,rs);
		if(ret >= mo)	ret -= mo;
		int L = max(ql,l), R = min(qr,r);
		ret = (1LL * t[x].lh * (RS[R - l + 1] - RS[L - l] + mo) + ret) % mo;
		ret = (1LL * t[x].rh * (RS[r - L + 1] - RS[r - R] + mo) + ret) % mo;
		return ret;
	}
	void work(int x,int y){
		int dis = d[x] + d[y] - 2 * d[lca(x,y)];
		int dx = 0,dy = dis,flag = 0,nx,ny;
		rt[++ curtot] = rt[cur];
		cur = curtot;
		for(;top[x] != top[y];x = fa[nx]){
			nx = top[x];
			ny = top[y];
			if(d[nx] < d[ny])	swap(nx,ny),swap(x,y),swap(dx,dy),flag ^= 1;
			ql = pos[rank[nx]];
			qr = pos[rank[x]];
			if(!flag){
				S = _R[dx];
				dx += d[x] - d[nx] + 1;
				modifyR(rt[cur],rt[cur],1,n);
			}else{
				S = _R[dx - d[x] + d[nx]];
				dx -= d[x] - d[nx] + 1;
				modifyL(rt[cur],rt[cur],1,n);
			}
		}
		if(d[x] < d[y])	swap(x,y),swap(dx,dy),flag ^= 1;
		ql = pos[rank[y]];
		qr = pos[rank[x]];
		if(!flag){
			S = _R[dx];
			modifyR(rt[cur],rt[cur],1,n);
		}else{
			S = _R[dy];
			modifyL(rt[cur],rt[cur],1,n);
		}
	}
	int query(int x,int y){
		int nx,ny,ret = 0;
		for(;top[x] != top[y];x = fa[nx]){
			nx = top[x];
			ny = top[y];
			if(d[nx] < d[ny])	swap(nx,ny),swap(x,y);
			ql = pos[rank[nx]];
			qr = pos[rank[x]];
			ret += ask(1,n,rt[cur]);
			if(ret >= mo)	ret -= mo;
		}
		if(d[x] < d[y])	swap(x,y);
		ql = pos[rank[y]];
		qr = pos[rank[x]];
		ret += ask(1,n,rt[cur]);
		if(ret >= mo)	ret -= mo;
		return ret;
	}
	int queryLR(int l,int r){
		ql = l;
		qr = r;
		return ask(1,n,rt[cur]);
	}
}A,B;

int calc(int l,int r){
	int an = A.queryLR(l,r) - B.queryLR(l,r);
	if(an < 0)	an += mo;
	return 1LL * an * trans % mo;
}
int main(){
//	freopen("FIBTREE_11.in","r",stdin);
	int r,Q;
	read(n);	read(Q);
	A.initR(R1);
	B.initR(R2);
	int x,y;
	cl(h,-1);
	rep(i,1,n - 1){
		read(x);	read(y);
		ae(x,y);	ae(y,x);
		e[i] = (edge){x,y};
	}
	pre(1);
	cl(h,-1);	ee = 0;
	rep(i,1,n - 1){
		if(d[e[i].x] > d[e[i].y])	swap(e[i].x,e[i].y);
		if(fir[e[i].x] != e[i].y)	ae(e[i].x,e[i].y);
	}
	rep(i,1,n)	if(fir[i])	ae(i,fir[i]);
	dfs(1);
	rep(i,1,n)	anc[0][i] = fa[i],pos[rank[i]] = pp[i];
	rep(j,1,19)
		rep(i,1,n)
			anc[j][i] = anc[j - 1][anc[j - 1][i]];
	char op[3];
	rootA[0] = rootB[0] = 0;
	int an,la = 0; 
	rep(i,1,Q){
		scanf("%s", op);
		if(op[0] == 'Q'){
			read(x);	read(y);
			x ^= la;
			if(op[1] == 'C'){
				an = A.query(x,y) - B.query(x,y);
				if(an < 0)	an += mo;
				an = 1LL * an * trans % mo;
				println(la = an);
			}else{
				if(y == x){
					println(la = calc(1,n));
				}else	if((ed[x] < st[y] || ed[y] < st[x]) || (st[x] <= st[y] && ed[x] >= ed[y])){
					println(la = calc(st[y],ed[y]));
				}else{ 
					int t = x;
					for(int k = d[t] - d[y] - 1,j = 0;k;k >>= 1,j ++)	if(k & 1)	t = anc[j][t];
					int an = calc(1,st[t] - 1) + calc(ed[t] + 1,n);
					if(an >= mo)	an -= mo;
					println(la = an);
				}
			}
		}else	if(op[0] == 'A'){
			read(x);	read(y);
			x ^= la;
			A.work(x,y);
			B.work(x,y);
		}else{
			read(x);
			x ^= la;
			A.cur = rootA[x];
			B.cur = rootB[x];
		}
		rootA[i] = A.cur;
		rootB[i] = B.cur;
	//	cout << i << " " << A.tot << endl;
	}
	return 0;
}