#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 42;

int len[maxn], link[maxn];
int state[maxn];
map<char, int> to[maxn];
int last, sz;

void add_letter(char c)
{
    int p = last;
    last = sz++;
    len[last] = len[p] + 1;
    state[len[last]] = last;
    for(; to[p][c] == 0; p = link[p])
        to[p][c] = last;
    if(to[p][c] == last)
        return;
    int q = to[p][c];
    if(len[q] == len[p] + 1)
    {
        link[last] = q;
        return;
    }
    int cl = sz++;
    to[cl] = to[q];
    link[cl] = link[q];
    len[cl] = len[p] + 1;
    link[last] = link[q] = cl;
    for(; to[p][c] == q; p = link[p])
        to[p][c] = cl;
}

const int logn = 18;
vector<int> g[maxn];
int in[maxn], out[maxn];
int up[maxn][logn];
int t;

void dfs(int v = 0)
{
    in[v] = ++t;
    for(auto u: g[v])
    {
        up[u][0] = v;
        for(int i = 1; i < logn; i++)
            up[u][i] = up[up[u][i - 1]][i - 1];
        dfs(u);
    }
    out[v] = t + 1;
}

multiset<int> lens[4 * maxn];

void add(int t, int p, int c, int v = 1, int l = 0, int r = maxn)
{
    if(t == 1)
        lens[v].insert(c);
    if(t == -1)
        lens[v].erase(lens[v].find(c));
    if(r - l == 1)
        return;
    int m = (l + r) / 2;
    if(p < m)
        add(t, p, c, 2 * v, l, m);
    else
        add(t, p, c, 2 * v + 1, m, r);
}

vector<int> ans;

void get(int a, int b, int k, int v = 1, int l = 0, int r = maxn)
{
    if(a <= l && r <= b)
    {
        auto it = lens[v].begin();
        for(int i = 0; i <= k && it != lens[v].end(); i++, it++)
            ans.push_back(*it);
        return;
    }
    if(r <= a || b <= l)
        return;
    int m = (l + r) / 2;
    get(a, b, k, 2 * v, l, m);
    get(a, b, k, 2 * v + 1, m, r);
}

int get(int ln, int pos)
{
    int v = state[pos];
    for(int i = logn - 1; i >= 0; i--)
        if(len[link[up[v][i]]] >= ln)
            v = up[v][i];
    if(len[link[v]] >= ln)
        v = up[v][0];
    return v;
}

ordered_set lns[maxn];

void init()
{
    for(int i = 0; i < sz; i++)
    {
        memset(up[i], 0, sizeof(up[i]));
        to[i].clear();
        g[i].clear();
        in[i] = out[i] = 0;
        len[i] = link[i] = 0;
        state[i] = 0;
        lns[i].clear();
    }
    sz = 1;
    last = 0;
    t = 0;
}

signed main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--)
    {
        init();
        string s;
        cin >> s;
        for(auto c: s)
            add_letter(c);
        for(int i = 1; i < sz; i++)
            g[link[i]].push_back(i);
        dfs();
        int q;
        cin >> q;
        while(q--)
        {
            int t, x, p;
            cin >> t >> x >> p;
            p++;
            int v = get(x, p);
            if(t == 1)
            {
                if(lns[v].find(x) != lns[v].end())
                    continue;
                add(1, in[v], x);
                lns[v].insert(x);
            }
            if(t == 2)
            {
                if(lns[v].find(x) == lns[v].end())
                    continue;
                add(-1, in[v], x);
                lns[v].erase(x);
            }
            if(t == 3)
            {
                int k;
                cin >> k;
                if(lns[v].size() - lns[v].order_of_key(x) >= k)
                {
                    cout << *lns[v].find_by_order(lns[v].order_of_key(x) + k - 1) << "\n";
                    continue;
                }
                else
                {
                    k -= lns[v].size() - lns[v].order_of_key(x);
                }
                get(in[v] + 1, out[v], k + 1);
                sort(ans.begin(), ans.end());
                if(k > ans.size())
                    cout << -1 << "\n";
                else
                    cout << ans[k - 1] << "\n";
                ans.clear();

            }
        }
    }
    return 0;
}