犯了sb错误,kth忘记均摊了。

int kth(int k) {
    int x = root;
    while (233) {
        int sz = siz[lc]; if (sz >= k) x = lc;
        else if (sz + 1 < k) k -= sz + 1, x = rc;
        else return splay(x), x;
    } 
} 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <iostream>
#include <ctime>
#include <bitset>
#define gc getchar()
#define ll long long
#define il inline
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repn(i, b, a) for (int i = b; i >= a; --i)
#define ite iterator
#define eps 1e-8
#define ull unsigned long long 

using namespace std;

template<class o> il void qr(o &x) {
    x = 0; char c = gc; int f = 1;
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = gc;}
    while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = gc;}
    x *= f;
}

template<class o> void qw(o x) {
    if(x / 10) qw(x / 10); putchar(x % 10 + 48);
}

template<class o> void pr1(o x) {
    if (x < 0) putchar('-'), x = -x;
    qw(x); putchar(' ');
}

template<class o> void pr2(o x) {
    if (x < 0) putchar('-'), x = -x;
    qw(x); puts("");
}
/* code */

const int N = 3e5 + 5;

namespace Splay {
    int fa[N], ch[N][2], id[N], siz[N], len, root;
    #define lc ch[x][0]
    #define rc ch[x][1]
    il void upd(int x) {siz[x] = siz[lc] + siz[rc] + 1;}
    il int son(int x) {return ch[fa[x]][1] == x;}
    void rotate(int x) {
        int y = fa[x], z = fa[y], w = !son(x), o = ch[x][w]; ch[y][w ^ 1] = o; if (o) fa[o] = y;
        if (z) ch[z][son(y)] = x; fa[x] = z; ch[x][w] = y; fa[y] = x; upd(y); upd(x);
    } void splay(int x, int rt = 0) {
        if (!rt) root = x; for (int y = fa[x]; y != rt; rotate(x), y = fa[x]) 
            if (fa[y] != rt) son(x) ^ son(y) ? rotate(x) : rotate(y);
    } int kth(int k) {
        int x = root;
        while (233) {
            int sz = siz[lc]; if (sz >= k) x = lc;
            else if (sz + 1 < k) k -= sz + 1, x = rc;
            else return splay(x), x;
        } 
    } int rak(int x) {splay(x); return siz[lc] + 1;}
    void insert(int k, int i) {
        if (!root) {root = ++len, id[len] = i; upd(len); return ;}
        if (!k) {
            int x = kth(1); splay(x); 
            int y = ++len; fa[x] = y; ch[y][1] = x; id[y] = i; root = y;
            upd(y); splay(y); 
        } else if (k == len) {
            int x = kth(len); splay(x);
            int y = ++len; fa[x] = y; ch[y][0] = x; id[y] = i; root = y;
            upd(y); splay(y);
        } else {
            int x = kth(k); splay(x); int y = rc; 
            while (ch[y][0]) y = ch[y][0]; splay(y, x);
            int z = ++len; fa[z] = y; ch[y][0] = z; id[z] = i;
            upd(z); upd(y); upd(x); splay(z);
        }
    }
    #undef lc 
    #undef rc
}

char s[N];
int pos[N]; ull pw[N];

void init(int n) {
    pw[0] = 1; for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 29;
}    

struct Seg {
    int siz; ull h1;    
} t[N << 2]; 

#define lc p << 1
#define rc p << 1 | 1

void upd(int p) {
    t[p].h1 = t[lc].h1 * pw[t[rc].siz] + t[rc].h1;
    t[p].siz = t[lc].siz + t[rc].siz;
}

void modify(int p, int l, int r, int x, ull d) {
    if (l == r) {t[p].h1 = d; t[p].siz = 1; return ;}
    int mid = l + r >> 1; 
    if (x <= mid) modify(lc, l, mid, x, d);
    else modify(rc, mid + 1, r, x, d);
    upd(p);    
}

int ask(int p, int l, int r, int L, int R) {
    if (L <= l && R >= r) return t[p].siz;
    int mid = l + r >> 1, val = 0;
    if (L <= mid) val = ask(lc, l, mid, L, R);
    if (R > mid) val += ask(rc, mid + 1, r, L, R);
    return val;
}

struct node {
    int siz; ull h;
    node(int siz = 0, ull h = 0ull) : siz(siz), h(h) {}
};

node query(int p, int l, int r, int x, int les) {
    if (r < x) return node(0, 0ull);
    if (l >= x && t[p].siz <= les) return node(t[p].siz, t[p].h1);
    int mid = l + r >> 1; node nw = node(0, 0ull);     
    if (x <= mid) {
        nw = query(lc, l, mid, x, les);
        node rs = node(0, 0ull); if (nw.siz < les) rs = query(rc, mid + 1, r, x, les - nw.siz);
        nw.siz = nw.siz + rs.siz; nw.h *= pw[rs.siz];
        nw.h += rs.h; return nw;
    } return query(rc, mid + 1, r, x, les);
}

struct Query {
    int op, x; char d; int y;
} Q[N];

void solve() {
    scanf("%s", s + 1); int n = strlen(s + 1);
    int len = 0;
    rep (i, 1, n) {
        Splay::insert(i - 1, i);
        Q[++len] = (Query) {-1, 0, s[i], 0};
    }
    int m; qr(m);
    rep (i, 1, m) {
        char ss[20]; scanf("%s", ss + 1);
        if (ss[1] == 'Q') {
            int l, r; qr(l), qr(r);
            Q[++len] = (Query) {1, Splay::id[Splay::kth(l)], '0', Splay::id[Splay::kth(r)]};    
        } else if (ss[1] == 'R') {
            int x; qr(x); char ch[5]; scanf("%s", ch);
            Q[++len] = (Query) {2, x, ch[0], 0};
            Q[len].y = Splay::id[Splay::kth(x)];
        } else {
            int x; qr(x); char ch[5]; scanf("%s", ch);
            Q[++len] = (Query) {3, x, ch[0], 0};
            Splay::insert(x, len);
        }    
    } 
    init(Splay::len);
    rep (i, 1, Splay::len)
        pos[Splay::id[i]] = Splay::rak(i);
    int cc = Splay::len;
    rep (i, 1, n) modify(1, 1, cc, pos[i], Q[i].d - 'a' + 1);
    rep (i, n + 1, n + m) {
        if (Q[i].op == 1) {
            int l = pos[Q[i].x], r = pos[Q[i].y]; if (l > r) swap(l, r);
            int L = 0, R = ask(1, 1, cc, r, cc);
            while (L < R) {
                int mid = L + R + 1 >> 1;
                if (query(1, 1, cc, l, mid).h != query(1, 1, cc, r, mid).h) R = mid - 1;
                else L = mid;
            } pr2(L);
        } else if (Q[i].op == 2) {
            int x = pos[Q[i].y]; modify(1, 1, cc, x, Q[i].d - 'a' + 1);    
        } else {
            int x = pos[i]; modify(1, 1, cc, x, Q[i].d - 'a' + 1);    
        }
    }
}

int main() {
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    //int T; qr(T); while (T--) {
        solve();
    //}
    return 0;
}