914-F

#include <bits/stdc++.h>
using namespace std;

#define N 100010
#define M 400010
#define B 316
#define base 1009
#define mod 1000000009
#define fi first
#define se second
#define pb push_back
#define endl '\n'

typedef long long int ll;

struct NODE
{

    int sum, lef, rig;

};

int n, q;
string s, t;

string str;
int tam;

int SA[N];
int tempSA[N];

int RA[N];
int tempRA[N];

int accu[N];

int ant[N];
int LCP[N];
int tempLCP[N];
int where[N];

int pot[N];

int root[N];
vector< NODE > st;

pair< ll, int > sts[M];
pair< ll, int > stt[M];

vector< pair< int, int > > update;

void Init()
{

    pot[0] = 1;

    for(int i = 1;i < N;i++)
        pot[i] = (base * pot[i-1]) % mod;

    return;

}

void CS(int k)
{

    int sum = 0, temp, i;

    memset(accu, 0, sizeof accu);

    for(i = 0;i < tam;i++)
    {

        if(i + k < tam) accu[RA[i + k]]++;
        else            accu[0]++;

    }

    for(i = 0;i < N;i++)
    {

        temp = accu[i];
        accu[i] = sum;
        sum += temp;

    }

    for(i = 0;i < tam;i++)
    {

        if((SA[i]+k)<tam)   tempSA[accu[RA[SA[i]+k]]++]=SA[i];
        else                tempSA[accu[0]++] = SA[i];

    }

    for(i = 0;i < tam;i++) SA[i] = tempSA[i];

    return;

}

void buildSA(string &s)
{

    s.pb('$');
    tam = (int)(s.size());

    int cur, i, k;

    for(i = 0;i < tam;i++) SA[i] = i;
    for(i = 0;i < tam;i++) RA[i] = (int)(s[i]);

    for(k = 1;k < tam;k <<= 1)
    {

        CS(k);
        CS(0);

        cur = 0;

        tempRA[SA[0]] = cur;

        for(i = 1;i < tam;i++)
        {

            cur++;
            if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k]) cur--;
            tempRA[SA[i]] = cur;

        }

        for(i = 0;i < tam;i++) RA[i] = tempRA[i];

    }

    ant[SA[0]] = -1;
    for(i = 1;i < tam;i++) ant[SA[i]] = SA[i - 1];

    cur = 0;

    for(i = 0;i < tam;i++)
    {

        if(ant[i] == -1)
        {

            tempLCP[i] = 0;
            continue;

        }

        while(s[i + cur] == s[ant[i] + cur]) cur++;

        tempLCP[i] = cur;
        cur = max(cur - 1, 0);

    }

    for(i = 0;i < tam;i++) LCP[i] = tempLCP[SA[i]];
    for(i = 0;i < tam;i++) where[SA[i]] = i;

    return;

}

int Build(int l, int r)
{

    int idx = (int)(st.size());
    st.pb({0, -1, -1});

    if(l == r) return idx;

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

    int a = Build(l, mid);
    int b = Build(mid+1, r);

    st[idx].lef = a;
    st[idx].rig = b;

    st[idx].sum = st[st[idx].lef].sum + st[st[idx].rig].sum;

    return idx;

}

int Update(int idx, int l, int r, int pos, int val)
{

    int newIdx = (int)(st.size());
    st.pb(st[idx]);

    if(l == r)
    {

        st[newIdx].sum += val;
        return newIdx;

    }

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

    int p;

    if(pos <= mid)  p = Update(st[idx].lef, l, mid, pos, val);
    else            p = Update(st[idx].rig, mid+1, r, pos, val);

    if(pos <= mid)  st[newIdx].lef = p;
    else            st[newIdx].rig = p;

    st[newIdx].sum = st[st[newIdx].lef].sum + st[st[newIdx].rig].sum;

    return newIdx;

}

int Query(int idx, int l, int r, int a, int b)
{

    if(r < a || b < l) return 0;

    if(a <= l && r <= b) return st[idx].sum;

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

    return Query(st[idx].lef, l, mid, a, b) + Query(st[idx].rig, mid+1, r, a, b);

}

int Query(int a, int b, int l, int r)
{

    if(r < l) return 0;
    if(b < a) return 0;

    return Query(root[b], 0, n, l, r) - Query(root[a-1], 0, n, l, r);

}

void buildST()
{

    root[0] = Build(0, n);
    root[0] = Update(root[0], 0, n, where[0], 1);

    for(int i = 1;i <= n;i++) root[i] = Update(root[i-1], 0, n, where[i], 1);

    return;

}

void updateAll()
{

    s = t;
    buildSA(s);

    st.clear();
    buildST();

    for(int i = 0;i < M;i++) sts[i] = stt[i];

    update.clear();

    return;

}

pair< int, int > getRange(string &p)
{

    int a, b, na, nb, l, r, m, i;

    a = 0;
    b = n;

    for(i = 0;i < (int)(p.size());i++)
    {

        l = a;
        r = b;
        na = b+1;

        while(l <= r)
        {

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

            if(s[SA[m]+i] < p[i])
            {

                l = m + 1;

            }else
            {

                na = m;
                r = m - 1;

            }

        }

        l = a;
        r = b;
        nb = a-1;

        while(l <= r)
        {

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

            if(s[SA[m]+i] <= p[i])
            {

                nb = m;
                l = m + 1;

            }else
            {

                r = m - 1;

            }

        }

        a = na;
        b = nb;

        if(b < a) break;

    }

    return {a, b};

}

pair< ll, int > mergeHash(pair< ll, int > a, pair< ll, int > b)
{

    pair< ll, int > c;

    c.fi = (a.fi * pot[b.se] + b.fi) % mod;
    c.se = a.se + b.se;

    return c;

}

void buildHash(pair< ll, int > st[], int idx, int l, int r)
{

    if(l == r)
    {

        st[idx] = {(int)(t[l]), 1};
        return;

    }

    int nxt = (idx << 1);
    int mid = ((l + r) >> 1);

    buildHash(st, nxt, l, mid);
    buildHash(st, nxt+1, mid+1, r);

    st[idx] = mergeHash(st[nxt], st[nxt+1]);

    return;

}

void updateHash(pair< ll, int > st[], int idx, int l, int r, int pos)
{

    if(l == r)
    {

        st[idx] = {(int)(t[l]), 1};
        return;

    }

    int nxt = (idx << 1);
    int mid = ((l + r) >> 1);

    if(pos <= mid)  updateHash(st, nxt, l, mid, pos);
    else            updateHash(st, nxt+1, mid+1, r, pos);

    st[idx] = mergeHash(st[nxt], st[nxt+1]);

    return;

}

pair< ll, int > queryHash(pair< ll, int > st[], int idx, int l, int r, int a, int b)
{

    if(r < a || b < l) return {0LL, 0LL};

    if(a <= l && r <= b) return st[idx];

    int nxt = (idx << 1);
    int mid = ((l + r) >> 1);

    return mergeHash(queryHash(st, nxt, l, mid, a, b), queryHash(st, nxt+1, mid+1, r, a, b));

}

int Solv(int l, int r, string &p)
{

    int ans = 0, hp, a, b, t, i;

    pair< int, int > aux;

    set< int > positions;

    t = (int)(p.size());

    aux = getRange(p);
    a = aux.fi;
    b = aux.se;

    ans = Query(l, r-t+1, a, b);

    hp = 0;

    for(i = 0;i < t;i++)
        hp = (base * hp + (int)(p[i])) % mod;

    for(auto [pos, ch] : update)
    {

        a = max(0, pos - t + 1);
        b = pos;

        for(i = a;i <= b;i++) positions.insert(i);

    }

    for(auto i : positions)
    {

        if(n <= i+t-1) break;

        if(queryHash(sts, 1, 0, n-1, i, i+t-1).fi == hp) ans--;
        if(queryHash(stt, 1, 0, n-1, i, i+t-1).fi == hp) ans++;

    }

    positions.clear();

    return ans;

}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Init();

    int op, l, r, pos, i;

    char ch;

    string p;

    cin >> s;
    n = (int)(s.size());

    t = s;
    buildHash(stt, 1, 0, n-1);

    cin >> q;

    for(i = 0;i < q;i++)
    {

        if((i%B) == 0) updateAll();

        cin >> op;

        if(op == 1)
        {

            cin >> pos >> ch;
            pos--;

            t[pos] = ch;
            updateHash(stt, 1, 0, n-1, pos);

            update.pb({pos, ch});

            continue;

        }

        cin >> l >> r >> p;
        l--;
        r--;

        cout << Solv(l, r, p) << endl;

    }

    return 0;

}