#include <iostream>
#include <queue>
#include <string.h>
#define maxn 10005
using namespace std;
typedef pair<int,int> pii;
pii seg[maxn*4];
bool operator < (pii x, pii y) {
    return x.first < y.first;
}
priority_queue<int> buk[maxn];
void add(int l, int r, int d, int p, int v) {
    if ( r < p || l > p )    return;
    if ( l == r && l == p ) {
        buk[p].push(v);
        seg[d] = make_pair(buk[p].top(),p);
        return;
    }
    int mid = (l+r)>>1;
    add(l,mid,d<<1,p,v);
    add(mid+1,r,(d<<1)+1,p,v);
    pii x = seg[d<<1], y = seg[(d<<1)+1];
    if ( x.first == y.first ) seg[d] = (x.second>y.second ? x : y);
    else seg[d] = (x.first>y.first ? x : y);
}
void del(int l, int r, int d, int p) {
    if ( r < p || l > p )    return;
    if ( l == r && l == p ) {
        buk[p].pop();
        if ( !buk[p].empty() )    seg[d] = make_pair(buk[p].top(),p);
        else    seg[d] = make_pair(-1,0);
        return;
    }
    int mid = (l+r)>>1;
    del(l,mid,d<<1,p);
    del(mid+1,r,(d<<1)+1,p);
    pii x = seg[d<<1], y = seg[(d<<1)+1];
    if ( x.first == y.first ) seg[d] = (x.second>y.second ? x : y);
    else seg[d] = (x.first>y.first ? x : y);
}
pii query(int a, int b, int l, int r, int d) {
    if ( a > r || b < l )    return make_pair(-1,0);
    if ( a <= l && r <= b )    return seg[d];
    int mid = (l+r)>>1;
    pii x = query(a,b,l,mid,d<<1), y = query(a,b,mid+1,r,(d<<1)+1);
    if ( x.first == y.first ) return (x.second>y.second ? x : y);
    else    return (x.first>y.first ? x : y);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q, a, b, c;
    cin >> N >> Q;
    for ( int i=0; i<N*4; ++i )    seg[i].first = -1;
    while ( Q-- && cin >> a >> b >> c ) {
        if ( a ) {
            pii x = query(b,c,0,N-1,1);
            cout << x.first << '\n';
            if ( x.first != -1 )    del(0,N-1,1,x.second);
        }
        else add(0,N-1,1,b,c);
    }
}