大家好，我不会平衡树，所以我用线段树过了这一题。
其实就是一个 trick：SGT 不能维护插入操作，于是离线处理：先求出序列最后长度，再倒着做所有插入操作（可以将一开始的序列也视作若干次插入）。
先将序列上每个位置标为 ，于是插入到第 个数后面就变成了线段树上二分，找到第一个前缀和为 的位置，于是在最终序列中，这个数就是在这个位置，并将这个位置标记为 。
当然如果优美一点你会发现上述操作可以用 BIT 替代。
知道最后每个数在哪里，就可以直接维护所有的操作了。SGT 维护哈希值和平衡树类似，就是维护当前哈希值 和序列长度 ，此处不再赘述。一开始还没插入的位置长度 要设为 ，插入时再改为 ，哈希值正常维护即可。
需要注意的是，在处理询问的时候会发现我们似乎还要动态维护当前序列每个位置对应最终序列哪个位置。不过这个东西其实也是一个 BIT 上二分就能解决，不会影响复杂度。
因为只用了简单 SGT+BIT 所以跑得飞快，在没有刻意卡常的情况下进了最优解第一页。
code：
const ull base=20247161607;
int n,m,cur,b[N],rk[N],id[N];
ull c[107],pw[N];
mt19937 rnd(time(0));
char s[N];
struct node{
int op,x,y;
}d[N];
struct Tnode{
int len;ull h;
Tnode(int _len=0,ull _h=0):len(_len),h(_h){}
Tnode operator+(const Tnode &rhs)const{
return Tnode(len+rhs.len,h*pw[rhs.len]+rhs.h);
}
};
struct SGT{
Tnode tr[N<<2];
il void pushup(int o){
tr[o]=tr[o<<1]+tr[o<<1|1];
}
void update(int l,int r,int o,int x,int y){
if(l==r){
tr[o]=Tnode(1,c[y]);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y);
}else{
update(mid+1,r,o<<1|1,x,y);
}
pushup(o);
}
Tnode query(int l,int r,int o,int x,int y){
if(r<x||l>y||x>y){
return Tnode();
}
if(l>=x&&r<=y){
return tr[o];
}
int mid=(l+r)>>1;
return query(l,mid,o<<1,x,y)+query(mid+1,r,o<<1|1,x,y);
}
}T;
struct BIT{
int tr[N];
#define lb(x) ((x)&(-(x)))
il void upd(int x,int y){
while(x<=cur){
tr[x]+=y;
x+=lb(x);
}
}
il int find(int x){
int p=0,s=0;
drep(i,18,0){
if(p+(1<<i)<=cur&&s+tr[p+(1<<i)]<=x){
p+=1<<i;
s+=tr[p];
}
}
return p+1;
}
}R;
void Yorushika(){
scanf("%s",s+1),n=strlen(s+1);
rep(i,0,25){
c[i]=1ull*rnd()*rnd()*rnd()*rnd();
}
rep(i,1,n){
rk[i]=i-1;
}
read(m),cur=n;
rep(i,1,m){
char op[7];int x,y;
scanf("%s",op),read(x);
if(op[0]=='Q'){
read(y);
d[i]={0,x,y};
}else if(op[0]=='R'){
scanf("%s",op);
d[i]={1,x,op[0]-'a'};
}else{
scanf("%s",op);
d[i]={2,x,op[0]-'a'};
rk[id[i]=++cur]=x;
}
}
pw[0]=1;
rep(i,1,cur){
R.upd(i,1);
pw[i]=pw[i-1]*base;
}
drep(i,cur,1){
b[i]=R.find(rk[i]);
R.upd(b[i],-1);
}
rep(i,1,n){
T.update(1,cur,1,b[i],s[i]-'a');
R.upd(b[i],1);
}
int len=n;
rep(i,1,m){
if(d[i].op==0){
int x=R.find(d[i].x-1),y=R.find(d[i].y-1);
int l=1,r=min(len-d[i].x+1,len-d[i].y+1),ans=0;
while(l<=r){
int mid=(l+r)>>1;
int X=R.find(d[i].x+mid-2),Y=R.find(d[i].y+mid-2);
if(T.query(1,cur,1,x,X).h==T.query(1,cur,1,y,Y).h){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
printf("%d\n",ans);
}else if(d[i].op==1){
int x=R.find(d[i].x-1);
T.update(1,cur,1,x,d[i].y);
}else{
T.update(1,cur,1,b[id[i]],d[i].y);
R.upd(b[id[i]],1);
len++;
}
}
}
signed main(){
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
