#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_NODES 16000000
#define MAX_NODES2 16000000
#define mod 1000000009
#define sqrt5 383008016
#define maxn 200000 + 5

int A, X, Y, Xback, Yback, Inv[4], pwr[4][100000 + 5], fib[100000 + 5], fibs[100000 + 5];

struct node {
	int d[4], sum[4], st_add, st_sum, sd[4], ssum[4];
	node *l, *r;
} all[MAX_NODES];
node* root[maxn];

struct infonode {
	node *ver;
	infonode *l, *r;
} all2[MAX_NODES2];
int hp2, cver;
infonode *vroot[maxn], *cur_root;

infonode* init2 (int l, int r) {
	infonode* me = &all2[hp2++];
	if (l < r) {
		me -> l = init2(l, (l + r) / 2);
		me -> r = init2((l + r) / 2 + 1, r);
	} else me -> ver = root[l];
	return me;
}

infonode* change (infonode* me, int nl, int nr, int j, node* she) {
	infonode* you = &all2[hp2++];
	you -> l = me -> l, you -> r = me -> r;
	if (nl == nr) {
		you -> ver = she;
		return you;
	}
	if (((nl + nr) >> 1) >= j) you -> l = change(me -> l, nl, (nl + nr) >> 1, j, she); else
							   you -> r = change(me -> r, ((nl + nr) >> 1) + 1, nr, j, she);
	return you;
}

node* getroot (infonode* me, int nl, int nr, int j) {
	if (nl == nr) return me -> ver;
	if (((nl + nr) >> 1) >= j) return getroot(me -> l, nl, (nl + nr) >> 1, j); else
							   return getroot(me -> r, (nl + nr) / 2 + 1, nr, j);
}

int hp, n, m, i;

node* init (int l, int r) {
	node* me = &all[hp++];
	if (l < r) {
		me -> l = init(l, (l + r) >> 1);
		me -> r = init(((l + r) >> 1) + 1, r);
	}
	return me;
}

int pw (int k, int p, int m) {
	if (p == 1) return k % m;
	int q = pw(k, p / 2, m);
	q = (q * 1LL * q) % m;
	if (p % 2) q = (q * 1LL * k) % m;
	return q;
}

void calc_constants () {
	A = ((3 + sqrt5) * 1LL * pw(5 + sqrt5, mod - 2, mod)) % mod;
	X = ((1 + sqrt5) * 1LL * pw(2, mod - 2, mod)) % mod;
	Y = ((1 - sqrt5 + mod) * 1LL * pw(2, mod - 2, mod)) % mod;
	Inv[0] = pw(X - 1, mod - 2, mod);
	Inv[1] = pw(Y - 1, mod - 2, mod);
	Xback = pw(X, mod - 2, mod);
	Yback = pw(Y, mod - 2, mod);
	Inv[2] = pw(Xback - 1, mod - 2, mod);
	Inv[3] = pw(Yback - 1, mod - 2, mod);
}

int gp_sum (int b1, int n, int idx) {
	return ((b1 * 1LL * (pwr[idx][n] - 1)) % mod * 1LL * Inv[idx]) % mod;
}

void anata_wa_watashi (node *you, node *me) {
	for(int j = 0; j < 4; j++) {
		you -> d[j] = me -> d[j];
		you -> sum[j] = me -> sum[j];
		you -> sd[j] = me -> sd[j];
		you -> ssum[j] = me -> ssum[j];
	}
	you -> st_sum = me -> st_sum;
	you -> st_add = me -> st_add;
	you -> l = me -> l;
	you -> r = me -> r;
}

node* add_prog_persistent (node* me, int nl, int nr, int l, int r, int d, int idx) {
	if (nl > r || nr < l) return me;
	if (l <= nl && nr <= r) {
		node* you = &all[hp++]; 
		anata_wa_watashi(you, me);
		int dt = (d * 1LL * pwr[idx][nl - l]) % mod;
		you -> d[idx] = (you -> d[idx] + dt) % mod;
		you -> sum[idx] = (you -> sum[idx] + gp_sum(dt, nr - nl + 1, idx)) % mod;
		return you;
	}
	node* you = &all[hp++];
	anata_wa_watashi(you, me);
	int cl = max(nl, l), ch = min(nr, r);
	you -> sum[idx] = (you -> sum[idx] + gp_sum(d, ch - l + 1, idx) - gp_sum(d, cl - l, idx) + 1LL * mod) % mod;
	you -> l = add_prog_persistent(you -> l, nl, (nl + nr) >> 1, l, r, d, idx);
	you -> r = add_prog_persistent(you -> r, ((nl + nr) >> 1) + 1, nr, l, r, d, idx);
	return you;
}

node* add_prog (node* me, int nl, int nr, int l, int r, int d, int idx) {
	if (nl > r || nr < l) return me;
	if (l <= nl && nr <= r) {
		int dt = (d * 1LL * pwr[idx][nl - l]) % mod;
		me -> d[idx] = (me -> d[idx] + dt) % mod;
		me -> sum[idx] = (me -> sum[idx] + gp_sum(dt, nr - nl + 1, idx)) % mod;
		return me;
	}
	int cl = max(nl, l), ch = min(nr, r);
	me -> sum[idx] = (me -> sum[idx] + gp_sum(d, ch - l + 1, idx) - gp_sum(d, cl - l, idx) + 1LL * mod) % mod;
	me -> l = add_prog(me -> l, nl, (nl + nr) >> 1, l, r, d, idx);
	me -> r = add_prog(me -> r, ((nl + nr) >> 1) + 1, nr, l, r, d, idx);
	return me;
}

node* add_subtree_persistent (node* me, int nl, int nr, int l, int r, int d, int idx) {
	if (nl > r || nr < l) return me;
	if (l <= nl && nr <= r) {
		node* you = &all[hp++];
		anata_wa_watashi(you, me);
		int dt = (d * 1LL * pwr[idx][nl - l]) % mod;
		you -> sd[idx] = (you -> sd[idx] + dt) % mod;
		you -> ssum[idx] = (you -> ssum[idx] + gp_sum(dt, nr - nl + 1, idx)) % mod;
		return you;
	}
	node* you = &all[hp++];
	anata_wa_watashi(you, me);
	int cl = max(nl, l), ch = min(nr, r);
	you -> ssum[idx] = (you -> ssum[idx] + gp_sum(d, ch - l + 1, idx) - gp_sum(d, cl - l, idx) + 1LL * mod) % mod;
	you -> l = add_subtree_persistent(you -> l, nl, (nl + nr) >> 1, l, r, d, idx);
	you -> r = add_subtree_persistent(you -> r, ((nl + nr) >> 1) + 1, nr, l, r, d, idx);
	return you;
}


node* add_subtree (node* me, int nl, int nr, int l, int r, int d, int idx) {
	if (nl > r || nr < l) return me;
	if (l <= nl && nr <= r) {
		int dt = (d * 1LL * pwr[idx][nl - l]) % mod;
		me -> sd[idx] = (me -> sd[idx] + dt) % mod;
		me -> ssum[idx] = (me -> ssum[idx] + gp_sum(dt, nr - nl + 1, idx)) % mod;
		return me;
	}
	int cl = max(nl, l), ch = min(nr, r);
	me -> ssum[idx] = (me -> ssum[idx] + gp_sum(d, ch - l + 1, idx) - gp_sum(d, cl - l, idx) + 1LL * mod) % mod;
	me -> l = add_subtree(me -> l, nl, (nl + nr) >> 1, l, r, d, idx);
	me -> r = add_subtree(me -> r, ((nl + nr) >> 1) + 1, nr, l, r, d, idx);
	return me;
}

node* add_segtree (node* me, int nl, int nr, int l, int r, int k) {
	if (nl > r || nr < l) return me;
	if (l <= nl && nr <= r) {
		me -> st_add = (me -> st_add + k) % mod;
		return me;
	}
	me -> l = add_segtree(me -> l, nl, (nl + nr) >> 1, l, r, k);
	me -> r = add_segtree(me -> r, ((nl + nr) >> 1) + 1, nr, l, r, k);
	me -> st_sum = (1LL * me -> l -> st_sum + me -> r -> st_sum + me -> l -> st_add * 1LL * ((nl + nr) / 2 - nl + 1) + me -> r -> st_add * 1LL * (nr - (nl + nr) / 2)) % mod;
	return me;
}

node* add_segtree_persistent (node* me, int nl, int nr, int l, int r, int k) {
	if (nl > r || nr < l) return me;
	if (l <= nl && nr <= r) {
		node* you = &all[hp++];
		anata_wa_watashi(you, me);
		you -> st_add = (you -> st_add + k) % mod;
		return you;
	}
	node* you = &all[hp++];
	anata_wa_watashi(you, me);
	you -> l = add_segtree_persistent(you -> l, nl, (nl + nr) >> 1, l, r, k);
	you -> r = add_segtree_persistent(you -> r, ((nl + nr) >> 1) + 1, nr, l, r, k);
	you -> st_sum = (1LL * you -> l -> st_sum + you -> r -> st_sum + you -> l -> st_add * 1LL * ((nl + nr) / 2 - nl + 1) + you -> r -> st_add * 1LL * (nr - (nl + nr) / 2)) % mod;
	return you;
}

int findsum (node* me, int nl, int nr, int l, int r) {
	if (nl > r || nr < l) return 0;
	if (nl >= l && r >= nr) return (me -> sum[0] + me -> sum[1] + 1LL * me -> sum[2] + me -> sum[3]) % mod;
	int cl = max(nl, l), ch = min(nr, r), ret = 0;
	ret = (1LL * ret + gp_sum(me -> d[0], ch - nl + 1, 0) +
					   gp_sum(me -> d[1], ch - nl + 1, 1) +
					   gp_sum(me -> d[2], ch - nl + 1, 2) +
					   gp_sum(me -> d[3], ch - nl + 1, 3) +
						- gp_sum(me -> d[0], cl - nl, 0) 
						- gp_sum(me -> d[1], cl - nl, 1) 
						- gp_sum(me -> d[2], cl - nl, 2)
						- gp_sum(me -> d[3], cl - nl, 3) + mod + mod + mod + mod) % mod;
	ret = (ret + findsum(me -> l, nl, (nl + nr) >> 1, l, r)) % mod;
	ret = (ret + findsum(me -> r, ((nl + nr) >> 1) + 1, nr, l, r)) % mod;
	return ret;
}

int findsubtreesum (node* me, int nl, int nr, int l, int r) {
	if (nl > r || nr < l) return 0;
	if (nl >= l && r >= nr) return (me -> ssum[0] + me -> ssum[1] + 1LL * me -> ssum[2] + me -> ssum[3]) % mod;
	int cl = max(nl, l), ch = min(nr, r), ret = 0;
	ret = (1LL * ret + gp_sum(me -> sd[0], ch - nl + 1, 0) +
		   gp_sum(me -> sd[1], ch - nl + 1, 1) +
		   gp_sum(me -> sd[2], ch - nl + 1, 2) +
		   gp_sum(me -> sd[3], ch - nl + 1, 3) +
		   - gp_sum(me -> sd[0], cl - nl, 0) 
		   - gp_sum(me -> sd[1], cl - nl, 1) 
		   - gp_sum(me -> sd[2], cl - nl, 2)
		   - gp_sum(me -> sd[3], cl - nl, 3) + mod + mod + mod + mod) % mod;
	ret = (ret + findsubtreesum(me -> l, nl, (nl + nr) >> 1, l, r)) % mod;
	ret = (ret + findsubtreesum(me -> r, ((nl + nr) >> 1) + 1, nr, l, r)) % mod;
	return ret;
}

int findsegtreesum (node* me, int nl, int nr, int l, int r, int sumadd) {
	if (nl > r || nr < l) return 0;
	if (nl >= l && r >= nr) return (me -> st_sum + (sumadd * 1LL * (nr - nl + 1))) % mod;
	int ret = 0;
	ret = (ret + findsegtreesum(me -> l, nl, (nl + nr) >> 1, l, r, (sumadd + me -> l -> st_add) % mod)) % mod;
	ret = (ret + findsegtreesum(me -> r, (nl + nr) / 2 + 1, nr, l, r, (sumadd + me -> r -> st_add) % mod)) % mod;
	return ret;
}

int x, y, k, lastans, was[maxn], subtree[maxn], f[maxn], t[maxn], p[maxn], ii, up[maxn][20], j, depth[maxn], chain[maxn], heavy[maxn], chains;
int sz[maxn], top[maxn], place_in_chain[maxn], l, r, lf, rf, tin[maxn], tout[maxn], timer, length, totsum, q, ref[maxn], ts[maxn];
char ch;

void dfs (int k) {
	tin[k] = ++timer;
	was[k] = 1;
	subtree[k] = 1;
	int q = f[k];
	while (q > 0) {
		if (!was[t[q]]) {
			up[t[q]][0] = k;
			for(j = 1; j < 17; j++) up[t[q]][j] = up[up[t[q]][j - 1]][j - 1];
			depth[t[q]] = 1 + depth[k];
			dfs(t[q]);
			subtree[k] += subtree[t[q]];
		}
		q = p[q];
	}
	int mx = -1, mq = -1;
	q = f[k];
	while (q > 0) {
		if (depth[t[q]] > depth[k] && subtree[t[q]] > mx) {
			mx = subtree[t[q]];
			mq = q;
		}
		q = p[q];
	}
	if (mq > -1) {
		heavy[mq] = 1;
		if (mq % 2) heavy[mq + 1] = 1; else heavy[mq - 1] = 1;
		if (!chain[t[mq]]) {
			chain[t[mq]] = ++chains;
			top[chains] = t[mq];
			sz[chains] = 1;
			place_in_chain[t[mq]] = 1;
		}
		chain[k] = chain[t[mq]];
		top[chain[k]] = k;
		++sz[chain[k]];
		place_in_chain[k] = sz[chain[k]];
	}
	tout[k] = ++timer;
}

void hl_build () {
	for(i = 0; i < 17; i++) up[1][i] = 1;
	dfs(1);
	for(i = 1; i <= n; i++) if (!chain[i]) {
		chain[i] = ++chains;
		top[chains] = i;
		sz[chains] = 1;
		place_in_chain[i] = 1;
	}
	for(i = 1; i <= chains; i++) root[i] = init(1, sz[i]);
	vroot[0] = init2(1, chains);
}

void go_up (int k, int dest, int cur_a, int cur_ar, int prev) { 
	int add;
	
	node* cur_chain_root;
	
	if (chain[k] == chain[dest]) {
		int l = place_in_chain[k];
		r = place_in_chain[dest];
	
		cur_chain_root = add_prog_persistent(getroot(cur_root, 1, chains, chain[k]), 1, sz[chain[k]], l, r, cur_a, 0);
		
		cur_chain_root = add_prog(cur_chain_root, 1, sz[chain[k]], l, r, cur_ar, 1);
		
		if (l < r) {
			if (prev == -1) add = 0; else add = fibs[prev];
			cur_chain_root = add_subtree_persistent(cur_chain_root, 1, sz[chain[k]], l, r - 1, ((cur_a * 1LL * pwr[0][1]) % mod * Inv[0]) % mod, 0);
			cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r - 1, ((cur_ar * 1LL * pwr[1][1]) % mod * Inv[1]) % mod, 1);
			int tmp = ((mod - cur_a) * 1LL * Inv[0] + (mod - cur_ar) * 1LL * Inv[1] + add) % mod;
			cur_chain_root = add_segtree(cur_chain_root, 1, sz[chain[k]], l, r - 1, tmp);
		}
		
		cur_root = change(cur_root, 1, chains, chain[k], cur_chain_root);
		
	} else {
		int l = place_in_chain[k];
		r = sz[chain[k]];
		
		cur_chain_root = add_prog_persistent(getroot(cur_root, 1, chains, chain[k]), 1, sz[chain[k]], l, r, cur_a, 0);		
		cur_chain_root = add_prog(cur_chain_root, 1, sz[chain[k]], l, r, cur_ar, 1);
	
		if (prev == -1) add = 0; else add = fibs[prev];		
		cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r, ((cur_a * 1LL * pwr[0][1]) % mod * Inv[0]) % mod, 0);
		cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r, ((cur_ar * 1LL * pwr[1][1]) % mod * Inv[1]) % mod, 1);
		int tmp = ((mod - cur_a) * 1LL * Inv[0] + (mod - cur_ar) * 1LL * Inv[1] + add) % mod;
		cur_chain_root = add_segtree(cur_chain_root, 1, sz[chain[k]], l, r, tmp);
		
		cur_root = change(cur_root, 1, chains, chain[k], cur_chain_root);
		
		cur_a = (cur_a * 1LL * pwr[0][r - l + 1]) % mod;
		cur_ar = (cur_ar * 1LL * pwr[1][r - l + 1]) % mod;
		go_up(up[top[chain[k]]][0], dest, cur_a, cur_ar, prev + r - l + 1);
	}
}

void go_up2 (int k, int dest, int cur_a, int cur_ar, int last) {
	
	node* cur_chain_root;
	
	int add = 0;
	if (chain[k] == chain[dest]) {
		int l = place_in_chain[k];
		r = place_in_chain[dest] - 1;
		if (l > r) return ;
		cur_chain_root = add_prog_persistent(getroot(cur_root, 1, chains, chain[k]), 1, sz[chain[k]], l, r, cur_a, 2);
		cur_chain_root = add_prog(cur_chain_root, 1, sz[chain[k]], l, r, cur_ar, 3);
		
		add = (fibs[length - 1] - fibs[last] + mod) % mod;
		
		cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r, ((cur_a * 1LL * pwr[2][1]) % mod * Inv[2]) % mod, 2);
		cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r, ((cur_ar * 1LL * pwr[3][1]) % mod * Inv[3]) % mod, 3);
		int tmp = ((mod - cur_a) * 1LL * Inv[2] + (mod - cur_ar) * 1LL * Inv[3] + add) % mod;
		cur_chain_root = add_segtree(cur_chain_root, 1, sz[chain[k]], l, r, tmp);		
		
		cur_root = change(cur_root, 1, chains, chain[k], cur_chain_root);
		
	} else {
		int l = place_in_chain[k];
		r = sz[chain[k]];
		cur_chain_root = add_prog_persistent(getroot(cur_root, 1, chains, chain[k]), 1, sz[chain[k]], l, r, cur_a, 2);
		cur_chain_root = add_prog(cur_chain_root, 1, sz[chain[k]], l, r, cur_ar, 3);

		add = (fibs[length - 1] - fibs[last] + mod) % mod;
				
		cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r, ((cur_a * 1LL * pwr[2][1]) % mod * Inv[2]) % mod, 2);
		cur_chain_root = add_subtree(cur_chain_root, 1, sz[chain[k]], l, r, ((cur_ar * 1LL * pwr[3][1]) % mod * Inv[3]) % mod, 3);
		int tmp = ((mod - cur_a) * 1LL * Inv[2] + (mod - cur_ar) * 1LL * Inv[3] + add) % mod;
		cur_chain_root = add_segtree(cur_chain_root, 1, sz[chain[k]], l, r, tmp);		
		
		cur_root = change(cur_root, 1, chains, chain[k], cur_chain_root);
		
		cur_a = (cur_a * 1LL * pwr[2][r - l + 1]) % mod;
		cur_ar = (cur_ar * 1LL * pwr[3][r - l + 1]) % mod;
		go_up2(up[top[chain[k]]][0], dest, cur_a, cur_ar, last - (r - l + 1));
	}	
}

int tsumq (int k, int dest, bool fl) {
	if (chain[k] == chain[dest]) {
		int l = place_in_chain[k];
		r = place_in_chain[dest];
		if (!fl) --r;
		if (l > r) return 0;
		return findsum(getroot(cur_root, 1, chains, chain[k]), 1, sz[chain[k]], l, r);
	} else {
		int l = place_in_chain[k];
		r = sz[chain[k]];
		return (findsum(getroot(cur_root, 1, chains, chain[k]), 1, sz[chain[k]], l, r) + tsumq(up[top[chain[k]]][0], dest, fl)) % mod;
	}
}

void recalc_subtrees (int k, int tag) {
	node * cur_chain_root = getroot(cur_root, 1, chains, chain[k]);
	cur_chain_root = add_segtree_persistent(cur_chain_root, 1, sz[chain[k]], place_in_chain[k], sz[chain[k]], tag);
	cur_root = change(cur_root, 1, chains, chain[k], cur_chain_root);
	if (top[chain[k]] != 1) recalc_subtrees(up[top[chain[k]]][0], tag);
}

void addedge (int x, int y) {
	t[++ii] = y;
	p[ii] = f[x];
	f[x] = ii;
}

bool anc (int x, int y) {
	return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}

int lca (int x, int y) {
	if (anc(x, y)) return x;
	for(int i = 16; i + 1; i--) if (!anc(up[x][i], y)) x = up[x][i];
	return up[x][0];
}

int find_prevnode (int x, int y) {
	l = lca(x, y);
	if (l != y) return up[y][1];
	int d = depth[x] - depth[y] - 1;
	for(j = 16; j + 1; j--) if (d & (1 << j)) x = up[x][j];
	return x;
}

int main (int argc, char * const argv[]) {
//	freopen("input.txt", "r", stdin);
	calc_constants();	
	pwr[0][0] = pwr[1][0] = pwr[2][0] = pwr[3][0] = 1;
	for(i = 1; i < 100000 + 5; i++) pwr[0][i] = (pwr[0][i - 1] * 1LL * X) % mod;
	for(i = 1; i < 100000 + 5; i++) pwr[1][i] = (pwr[1][i - 1] * 1LL * Y) % mod; 	
	for(i = 1; i < 100000 + 5; i++) pwr[2][i] = (pwr[2][i - 1] * 1LL * Xback) % mod;
	for(i = 1; i < 100000 + 5; i++) pwr[3][i] = (pwr[3][i - 1] * 1LL * Yback) % mod;
	fib[0] = fib[1] = 1;
	for(i = 2; i < 100000 + 5; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
	fibs[0] = fib[0];
	for(i = 1; i < 100000 + 5; i++) fibs[i] = (fibs[i - 1] + fib[i]) % mod;
	scanf("%d %d", &n, &m);
	for(i = 1; i < n; i++) {
		scanf("%d %d", &x, &y);
		addedge(x, y);
		addedge(y, x);
	}
	hl_build();
	cver = 0;
	cur_root = vroot[0];
	
	lastans = 0;
	
	for(i = 1; i <= m; i++) {
		ch = getchar();
		while (ch < 'A' || ch > 'Z') ch = getchar();
		if (ch == 'A') {
			scanf("%d %d", &x, &y);
			x ^= lastans;
			l = lca(x, y);
			length = depth[x] + depth[y] - 2 * depth[l] + 1;
			go_up(x, l, A, 1 - A + mod, -1);			
			go_up2(y, l, (A * 1LL * pwr[0][length - 1]) % mod, ((1 - A + mod) * 1LL * pwr[1][length - 1]) % mod, length - 1);
			recalc_subtrees(l, fib[length + 1] - 1);
			totsum = (totsum + fib[length + 1] - 1) % mod;
			
			cver = i;
			vroot[cver] = cur_root;
			ref[i] = i;
			ts[i] = totsum;
		}
		if (ch == 'Q') {
			ref[i] = ref[i - 1];
			ch = getchar();
			if (ch == 'C') {
				scanf("%d %d", &x, &y);
				x ^= lastans;
				l = lca(x, y);
				
				lastans = (tsumq(x, l, 1) + tsumq(y, l, 0)) % mod;
				
				printf("%d\n", lastans);
			} else {
				if (ch == 'S') {
					scanf("%d %d", &x, &y);
					
					x ^= lastans;
					
					if (x == y) {
						lastans = totsum;
						printf("%d\n", totsum);
						continue;
					}
					
					q = find_prevnode(x, y);
					
					if (depth[q] < depth[y]) {				
						node * cur_chain_root = getroot(cur_root, 1, chains, chain[y]);
						int ans = findsubtreesum(cur_chain_root, 1, sz[chain[y]], place_in_chain[y], place_in_chain[y]);
						ans = (ans + findsegtreesum(cur_chain_root, 1, sz[chain[y]], place_in_chain[y], place_in_chain[y], cur_chain_root -> st_add)) % mod;
						printf("%d\n", ans);
						lastans = ans; 
					} else {
						node * cur_chain_root = getroot(cur_root, 1, chains, chain[q]);
						int ans = findsubtreesum(cur_chain_root, 1, sz[chain[q]], place_in_chain[q], place_in_chain[q]);
						ans = (ans + findsegtreesum(cur_chain_root, 1, sz[chain[q]], place_in_chain[q], place_in_chain[q], cur_chain_root -> st_add)) % mod;
						printf("%d\n", (totsum - ans + mod) % mod);		
						lastans = (totsum - ans + mod) % mod;
					}
					
				}
			}
		}
		if (ch == 'R') {
			scanf("%d", &x);
			x ^= lastans;
			cver = ref[x];
			cur_root = vroot[cver];
			totsum = ts[cver];
			ref[i] = cver;
		}
	}
    return 0;
}