/**************************************************************    Problem: 1014    User: BeiYu    Language: C++    Result: Accepted    Time:6580 ms    Memory:9320 kb****************************************************************/ #include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std; typedef unsigned long long LL;const int N = 200050;#define lc(o) d[o].ch[0]#define rc(o) d[o].ch[1]#define f(o) d[o].f#define h(o) d[o].h#define v(o) d[o].v#define s(o) d[o].s#define mid ((l+r)>>1) //char *ps=(char *)malloc(N<<3);inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; } LL p[N];char ch[N];struct SplayTree{    struct Node{        int ch[2],f;        LL h,v;int s;        void Init(LL hh,LL vv,int ss){ h=hh,v=vv,s=ss,ch[0]=ch[1]=f=0; }    }d[N];    int rt,cnt;         void PushUp(int o){        if(!o) return;        d[o].h=0;d[o].s=d[lc(o)].s+d[rc(o)].s+1;        h(o)=(LL)h(lc(o))+v(o)*p[s(lc(o))]+h(rc(o))*p[s(lc(o))+1];//      if(rc(o)!=0) h(o)=h(o)+h(rc(o));//      h(o)=h(o)+v(o)*p[d[rc(o)].s];//      if(lc(o)!=0) h(o)=h(o)+h(lc(o))*p[d[rc(o)].s+1];    }    void Build(int &o,int fa,int l,int r){        if(l>r) return;        o=++cnt;        d[o].Init(0,0,0);        if(ch[mid]>=‘a‘) d[o].v=ch[mid]-‘a‘+13;        f(o)=fa;        Build(lc(o),o,l,mid-1);        Build(rc(o),o,mid+1,r);        PushUp(o);    }//  int Build(int l,int r,int fa){//      if(l==r){//          d[l].Init(0,0,0);//          if(ch[l]>=‘a‘) d[l].v=d[l].h=ch[l]-‘a‘+1;//          d[l].s=1,f(l)=fa,PushUp(l);return l;//      }//      d[mid].Init(0,0,0);//      if(ch[mid]>=‘a‘) v(mid)=ch[mid]-‘a‘+1;f(mid)=fa;//      if(l<mid) lc(mid)=Build(l,mid-1,mid);//      if(r>mid) rc(mid)=Build(mid+1,r,mid);//      PushUp(mid);return mid;//  }    void Rot(int o){        int p=f(o),k=f(p),r=rc(p)==o;        if(k) d[k].ch[rc(k)==p]=o;        d[d[o].ch[r^1]].f=p,d[o].f=k;        d[p].ch[r]=d[o].ch[r^1],d[o].ch[r^1]=p,d[p].f=o;        PushUp(p),PushUp(o);    }    void DFS(int o){        if(lc(o)) DFS(lc(o));        cout<<o<<" "<<d[o].v<<" "<<d[o].h<<" "<<d[o].s<<endl;        cout<<" lc="<<lc(o)<<" rc="<<rc(o)<<" f="<<f(o)<<endl;        if(rc(o)) DFS(rc(o));    }    void Splay(int o,int g){        for(;f(o)!=g;){            int p=f(o),k=f(p);            if(k!=g) Rot((rc(p)==o)==(rc(k)==p)?p:o);//          cout<<"Ok Rot"<<endl;            Rot(o);        }if(!g) rt=o;//      cout<<"rt="<<rt<<endl;//      DFS(rt);    }    int findkth(int o,int k){        if(d[lc(o)].s>=k) return findkth(lc(o),k);        else if(d[lc(o)].s+1<k) return findkth(rc(o),k-d[lc(o)].s-1);        else return o;    }    void Insert(int x,LL v){        int p=findkth(rt,x),q=findkth(rt,x+1);        Splay(p,0),Splay(q,p);//      d[++cnt].Init(0,v,0);rt=cnt;//      rc(p)=0,f(p)=f(q)=rt,lc(rt)=p,rc(rt)=q;//      PushUp(p),PushUp(q),PushUp(rt);        d[++cnt].Init(0,v,0);        f(cnt)=q,lc(q)=cnt;        PushUp(cnt),PushUp(q),PushUp(p);    }    void Change(int x,LL v){        int o=findkth(rt,x);        Splay(o,0),d[o].v=v,PushUp(o);    }    void init(){//      fread(ps,1,N<<3,stdin);        p[0]=1;for(int i=1;i<N;i++) p[i]=(LL)p[i-1]*197;         d[0].Init(0,0,0);        scanf("%s",ch+2);int n=strlen(ch+2);        Build(rt,0,1,n+2);//      rt=Build(1,n+2,0);//      cout<<rt<<" "<<cnt<<endl;    }    LL Query(int u,int v){//      if(u>v) return -1;        u--,v++;        u=findkth(rt,u),v=findkth(rt,v);//      cout<<"Ok find "<<u<<" "<<v<<endl;        Splay(u,0),Splay(v,u);//      cout<<"Ok Splay"<<endl;        return h(lc(v));    }    void sol(){        char opt[5],c[5];int u,v;        for(int m=in();m--;){            scanf("%s",opt);//          cout<<opt<<"********"<<endl;            if(opt[0]==‘R‘) scanf("%d%s",&u,c),Change(u+1,c[0]-‘a‘+13);            else if(opt[0]==‘I‘) scanf("%d%s",&u,c),Insert(u+1,c[0]-‘a‘+13);            else {                u=in()+1,v=in()+1;                int l=0,r=min(cnt-v,cnt-u);//              cout<<"Start Q"<<endl<<"*********"<<endl;                while(l<=r){//                  cout<<"***\ncs mid="<<mid<<endl;//                  cout<<u<<" "<<mid<<" "<<Query(u,u+mid-1)<<endl;//                  cout<<v<<" "<<mid<<" "<<Query(v,v+mid-1)<<endl;                    if((LL)Query(u,u+mid-1)==Query(v,v+mid-1)) l=mid+1;                    else r=mid-1;                }printf("%d\n",r);            }//          cout<<opt<<" is ok"<<endl;        }    }}spl; int main(){//  freopen("in.in","r",stdin);//  freopen("out.out","w",stdout);    spl.init();//  cout<<"Finish init()"<<endl;//  spl.DFS(spl.rt);//  cout<<"Finish DFS()"<<endl;    spl.sol();//  cout<<"Finish sol()"<<endl;    return 0;}