#include <bits/stdc++.h>

 #define DEBUG 0

 #define mid (l+r>>1)

 #define MOD 1000000009

 #define Que(rt,x,y) que(rt,1,n,x,y)

 #define Len (dep[x]-dep[top[x]]+1)

 using namespace std;

 struct node

 {

     int f,s,F,S,sum;

     node(long long a,long long b,long long c,long long d,long long e)

     {

         f=a%MOD;s=b%MOD;F=c%MOD;S=d%MOD;sum=e%MOD;

     }

     node()

     {

     }

 } tr[];

 int ls[],rs[];

 int TIME,E,NODE,n,m,p,q,x,y;char ch;bool rev;

 int pos[],start[],en[];

 int dep[],top[],fa[],root[];

 int to[],nex[],fir[],size[];

 long long f[];

 int son(int x,int y)

 {

     while(dep[fa[top[y]]]>dep[x]) y=fa[top[y]];

     if(fa[top[y]]==x) return top[y];

     else return pos[start[x]+];

 }

 void add(int p,int q)

 {

     to[++E]=q;nex[E]=fir[p];fir[p]=E;

 }

 int build(int now,int fat)

 {

     fa[now]=fat;

     dep[now]=dep[fat]+;

     size[now]=;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fat)

         size[now]+=build(to[i],now);

     return size[now];

 }

 void pou(int now,int Top)

 {

     top[now]=Top;start[now]=++TIME;pos[TIME]=now;

     int id=;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fa[now])

         if(!id || size[to[i]]>size[id]) id=to[i];

     if(id) pou(id,Top);

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fa[now] && to[i]!=id)

         pou(to[i],to[i]);

     en[now]=TIME;

 }

 int lca(int x,int y)

 {

     for(;top[x]!=top[y];x=fa[top[x]])

         if(fa[top[x]]<fa[top[y]]) swap(x,y);

     return dep[x]>dep[y]?y:x;

 }

 long long fib(int F,int S,int x)

 {

     if(x==) return F;

     if(x==) return S;

     return (f[x-]*F+f[x-]*S)%MOD;

 }

 long long getsum(int now,int x,int y)

 {

     if(y==) return (tr[now].f+tr[now].F)%MOD;

     if(x== && y==) return ((tr[now].f+tr[now].F)%MOD+(tr[now].s+tr[now].S)%MOD)%MOD;

     if(x== && y==) return (tr[now].s+tr[now].S)%MOD;

     int F=(((y&?:-)*f[y-]*tr[now].F-(y&?:-)*f[y-]*tr[now].S)%MOD+MOD)%MOD,S=(((y&?-:)*f[y-]*tr[now].F+(y&?:-)*f[y-]*tr[now].S)%MOD+MOD)%MOD;

     return (fib(tr[now].f,tr[now].s,y+)-fib(tr[now].f,tr[now].s,x+)+MOD+fib(F,S,y-x+)-S+MOD)%MOD;

 }

 int que(int now,int l,int r,int x,int y)

 {

     if(!now) return ;

     if(l==x && r==y)

         return tr[now].sum;

     int ret=getsum(now,x-l+,y-l+);

     if(x<=mid) ret=(ret+que(ls[now],l,mid,x,min(y,mid)))%MOD;

     if(y>mid) ret=(ret+que(rs[now],mid+,r,max(mid+,x),y))%MOD;

     return ret;

 }

 int add(int acc,int l,int r,int x,int y,int st,bool rev)

 {

     int now=++NODE;

     if(NODE>) while();

     tr[now]=tr[acc];

     if(l==x && r==y)

     {

         if(rev) tr[now]=node(tr[acc].f,tr[acc].s,tr[acc].F+f[st],tr[acc].S+f[st-],tr[acc].sum+f[st+]-f[st+l-r+]+MOD);

         else tr[now]=node(tr[acc].f+f[st],tr[acc].s+f[st+],tr[acc].F,tr[acc].S,tr[acc].sum+f[st+r-l+]-f[st+]+MOD);

         ls[now]=ls[acc];rs[now]=rs[acc];

         return now;

     }

     if(x<=mid && y<=mid)

         ls[now]=add(ls[acc],l,mid,x,y,st,rev),rs[now]=rs[acc];

     else

     if(y>mid && x>mid)

         ls[now]=ls[acc],rs[now]=add(rs[acc],mid+,r,x,y,st,rev);

     else

     {

         ls[now]=add(ls[acc],l,mid,x,mid,st,rev);

         rs[now]=add(rs[acc],mid+,r,mid+,y,st+(rev?-:)*(mid-x+),rev);

     }

     tr[now].sum=(tr[ls[now]].sum+tr[rs[now]].sum+getsum(now,,r-l+))%MOD;

     return now;

 }

 int main()

 {

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

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

         scanf("%d%d",&p,&q),

         add(p,q),add(q,p);

     build(,);pou(,);

     f[]=;f[]=;

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

     {

         f[i]=f[i-]+f[i-];

         if(f[i]>MOD) f[i]-=MOD;

     }

     root[]=;NODE=;

     int lastans=;

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

     {

         root[i]=root[i-];

         char S[];

         scanf("%s",&S);

         if(S[]=='A')

         {

             scanf("%d%d",&x,&y);

             if(!DEBUG)

             x^=lastans;

             if(x>n) while();

             bool rev=;int len=,leng=dep[x]+dep[y]-*dep[lca(x,y)]+;

             for(;top[x]!=top[y];x=fa[top[x]])

             {

                 if(dep[top[x]]<dep[top[y]]) swap(x,y),rev^=;

                 if(rev) leng-=Len;else len+=Len;

                 root[i]=add(root[i],,n,start[top[x]],start[x],rev?leng+:len-,!rev);

             }

             if(dep[x]>dep[y]) swap(x,y),rev^=;

             root[i]=add(root[i],,n,start[x],start[y],rev?leng:len,rev);

         }

         if(S[]=='R')

         {

             scanf("%d",&x);

             if(!DEBUG)

             x^=lastans;

             if(x>=i) while();

             root[i]=root[x];

         }

         if(S[]=='Q')

         {

             scanf("%d%d",&x,&y);

             if(!DEBUG)

             x^=lastans;

             if(x>n) while();

             int t=lca(x,y);

             if(S[]=='S')

             if(x!=y)

             if(t==y)

             {

                 int tem=son(y,x);

                 lastans=(Que(root[i],,n)-Que(root[i],start[tem],en[tem])+MOD)%MOD;

             }

             else

                 lastans=Que(root[i],start[y],en[y]);

             else

                 lastans=Que(root[i],,n);

             else

             {

                 lastans=;

                 for(;top[x]!=top[y];x=fa[top[x]])

                 {

                     if(dep[top[x]]<dep[top[y]]) swap(x,y);

                     lastans+=Que(root[i],start[top[x]],start[x]);

                     lastans%=MOD;

                 }

                 if(dep[x]>dep[y]) swap(x,y);

                 lastans+=Que(root[i],start[x],start[y]);

                 lastans%=MOD;

             }

             printf("%d\n",lastans);

         }

     }

     return ;

 }