Add - Erase - GetMax from L -> R

//Make CSP great again
//You're as beautiful as the day I lost you
//New year, best wishes
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e6, M = 2e5;
int n, m;
string s[M + 1];
struct SegmentTree
{
    bitset<N + 1> used;
    vector<int> Tree[4 * N + 1], up[4 * N + 1];
    void Update(int v, int TreeL, int TreeR, int L, int R, int val)
    {
        if (L > R)
        {
            return ;
        }
        while(!up[v].empty() && used[up[v].back()])
        {
            up[v].pop_back();
        }
        up[v].push_back(val);
        if (TreeL == L && TreeR == R)
        {
            while(!Tree[v].empty() && used[Tree[v].back()])
            {
                Tree[v].pop_back();
            }
            Tree[v].push_back(val);
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        Update(v * 2, TreeL, mid, L, min(mid, R), val);
        Update(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, val);
    }
    int Get(int v, int TreeL, int TreeR, int L, int R)
    {
        if (L > R)
        {
            return -1;
        }
        int ret = -1;
        while(!Tree[v].empty() && used[Tree[v].back()])
        {
            Tree[v].pop_back();
        }
        if (!Tree[v].empty())
        {
            ret = max(ret, Tree[v].back());
        }
        if (TreeL == L && TreeR == R)
        {
            while(!up[v].empty() && used[up[v].back()])
            {
                up[v].pop_back();
            }
            if (!up[v].empty())
            {
                ret = max(ret, up[v].back());
            }
            return ret;
        }
        int mid = (TreeL + TreeR)/2;
        ret = max({ret, Get(v * 2, TreeL, mid, L, min(R, mid)), Get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R)});
        return ret;
    }
    void add(int L, int R, int val)
    {
        Update(1, 1, n, L, R, val);
    }
    int Query(int L, int R)
    {
        int t = Get(1, 1, n, L, R);
        if (t != -1)
        {
            used[t] = true;
        }
        return t;
    }
} Tree;
void read()
{
    cin >> n >> m;
}
void solve()
{
    for (int i = 1; i <= m; ++ i)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            cin >> s[i];
            int l, r;
            cin >> l >> r;
            ++l;
            ++r;
            Tree.add(l, r, i);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            ++l;
            ++r;
            int ret = Tree.Query(l, r);
            if (ret != -1)
            {
                cout << s[ret] << '\n';
            }
            else
            {
                cout << -1 << '\n';
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".out", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}