Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

char c[300010];

typedef long long ll;

#define BASE 19260817ll

#define MOD 1000000007ll

ll power[300010];

struct node

{

    int fa,c[2],siz;

    ll ch,hash;

    node(){fa = c[0] = c[1] = siz = 0;hash = 0ll;}

}t[300010];

int root;

int ptr = 0;

int newnode(){return ++ptr;}

void maintain(int rt)

{

    t[rt].siz = 1;t[rt].hash = t[rt].ch;

    if(t[rt].c[0] != 0){t[rt].siz += t[t[rt].c[0]].siz;t[rt].hash = (t[t[rt].c[0]].hash + t[rt].hash * power[t[t[rt].c[0]].siz] % MOD) % MOD;}

	if(t[rt].c[1] != 0){t[rt].hash = (t[rt].hash + t[t[rt].c[1]].hash * power[t[rt].siz] % MOD) % MOD;t[rt].siz += t[t[rt].c[1]].siz;}

	return;

}

void build(int &rt,int l,int r,int f)

{

    if(l > r)return;

    rt = newnode();

    t[rt].fa = f;

    int mid = ((l + r) >> 1);

    t[rt].ch = (int)c[mid];

    build(t[rt].c[0],l,mid - 1,rt);

    build(t[rt].c[1],mid + 1,r,rt);

    maintain(rt);

    return;

}

inline char getc()

{

	register char c = getchar();

	while(!isalpha(c))c = getchar();

	return c;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

void pt(int k)

{

	if(k == 0)return;

	pt(t[k].c[0]);

	cout << (char)t[k].ch;

	pt(t[k].c[1]);

	return;

}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	connect(x,z,fy);

	maintain(y);maintain(x);

	return;

}

void splay(int x,int &to)

{

	int des = t[to].fa;

	while(t[x].fa != des)

	{

		int y = t[x].fa;

		if(t[y].fa == des){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	to = x;

	return;

}

int find_kth(int k)

{

	int cur = root;

	while(true)

	{

		int ls = 0;

		if(t[cur].c[0] != 0)ls = t[t[cur].c[0]].siz;

		if(k <= ls)cur = t[cur].c[0];

		else if(k > ls + 1){cur = t[cur].c[1];k -= ls + 1;}

		else{return cur;}

	}

}

void insert()

{

	int p = read();

	char c = getc();

	splay(find_kth(p),root);

	int k = newnode();

	t[k].ch = (ll)c;

	connect(t[root].c[1],k,1);

	connect(k,root,1);

	maintain(k);

	maintain(root);

	return;

}

void change()

{

	int p = read();

	char c = getc();

	splay(find_kth(p),root);

	t[root].ch = (ll)c;

	maintain(root);

	return;

}

ll query(int l,int r)

{

	if(l > r)return 0;

	if(l == 1 && r == t[root].siz)return t[root].hash;

	if(l == 1){splay(find_kth(r + 1),root);return t[t[root].c[0]].hash;}

	if(r == t[root].siz){splay(find_kth(l - 1),root);return t[t[root].c[1]].hash;}

	splay(find_kth(l - 1),root);splay(find_kth(r + 1),t[root].c[1]);

	return t[t[t[root].c[1]].c[0]].hash;

}

int work()

{

	int a = read(),b = read();

	int l = 0,r = min(t[root].siz - b + 1,t[root].siz - a + 1),mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(query(a,a + mid - 1) == query(b,b + mid - 1))l = mid;

		else r = mid - 1;

	}

	return l;

}

int main()

{

    power[0] = 1;

    for(int i = 1;i < 300001;++i)power[i] = power[i - 1] * BASE % MOD;

    scanf("%s",c + 1);

    int l = strlen(c + 1);

    build(root,1,l,0);

    scanf("%d",&n);

    char ch;

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

    {

		ch = getc();

		if(ch == 'Q')printf("%d\n",work());

		if(ch == 'R')change();

		if(ch == 'I')insert();

	}

    return 0;

}