# 2. 题解

（这里面的 $233$可以改，最好大于字符集大小。。。不知道不是质数会不会有危害，没试过）

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef unsigned long long ULL;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct N {ULL d, sum; int f, s[2], sz;} e[NS];

char str[NS], opt[5];

int len, sz, root, q;

ULL data[NS], M[NS] = {1};

bool pos(int a)
{
return e[e[a].f].s[1] == a;
}

void pup(int a)
{
int l = e[a].s[0], r = e[a].s[1];
e[a].sz = e[l].sz + e[r].sz + 1;
e[a].sum = e[l].sum + M[e[l].sz] * e[a].d + M[e[l].sz + 1] * e[r].sum;
}

void rot(int a)
{
int f = e[a].f, g = e[f].f, p = pos(a), q = pos(f);
e[f].s[p] = e[a].s[!p], e[a].s[!p] = f, e[f].f = a;
if (e[f].s[p]) e[e[f].s[p]].f = f;
if (e[a].f = g) e[g].s[q] = a;
pup(f), pup(a);
}

void splay(int a, int t)
{
for (; e[a].f != t; rot(a))
if (e[e[a].f].f != t)
{
if (pos(a) ^ pos(e[a].f)) rot(a);
else rot(e[a].f);
}
if (!t) root = a;
}

int Build(int l, int r)
{
if (l > r) return 0;
int a = ++sz, mid = (l + r) >> 1;
e[a].s[0] = Build(l, mid - 1), e[a].s[1] = Build(mid + 1, r);
e[e[a].s[0]].f = e[e[a].s[1]].f = a;
e[a].d = data[mid], pup(a); return a;
}

int find_by_order(int k)
{
int a = root;
while (a)
{
if (k < e[e[a].s[0]].sz + 1) a = e[a].s[0];
else
{
k -= e[e[a].s[0]].sz + 1;
if (!k) return a;
a = e[a].s[1];
}
}
return 0;
}

void Get_Seg(int& l, int& r)
{
l = find_by_order(l), r = find_by_order(r + 2);
splay(l, 0), splay(r, l);
}

ULL Query(int l, int r)
{
Get_Seg(l, r); return e[e[r].s[0]].sum;
}

int LCQ(int x, int y)
{
if (x > y) swap(x, y);
int l = 0, r = (len - y + 1), mid;
while (l < r)
{
mid = (l + r + 1) >> 1;
if (Query(x, x + mid - 1) == Query(y, y + mid - 1)) l = mid;
else r = mid - 1;
}
return l;
}

void Refresh(int x, char c)
{
int l = x, r = x; Get_Seg(l, r);
e[e[r].s[0]].d = e[e[r].s[0]].sum = c - 'a';
pup(r), pup(l);
}

void Insert(int x, char c)
{
int l = x + 1, r = x; Get_Seg(l, r);
e[r].s[0] = ++sz, e[sz].f = r, e[sz].s[0] = e[sz].s[1] = 0;
e[sz].d = e[sz].sum = c - 'a', e[sz].sz = 1;
pup(r), pup(l);
}

int main(int argc, char const* argv[])
{
scanf("%s", str + 1), len = strlen(str + 1);
for (int i = 1; i <= len; i += 1) data[i + 1] = str[i] - 'a';
for (int i = 1; i <= NS - 5; i += 1) M[i] = M[i - 1] * 233;
root = Build(1, len + 2), IN(q);
while (q--)
{
int x, y;
scanf("%s", opt), IN(x);
if (opt[0] == 'Q') IN(y), printf("%d\n", LCQ(x, y));
else if (opt[0] == 'R') scanf("%s", opt), Refresh(x, opt[0]);
else scanf("%s", opt), Insert(x, opt[0]), len++;
}
return 0;
}