#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 1 << 18;

priority_queue <int> q[MAXN];

int it[MAXN * 2], N, M;
void scan(){
    cin >> N >> M;
}

void update ( int l, int r, int idx, int pos, int val ){
    if ( l > pos || r < pos )
        return;
    if ( l == r ){
        it[idx] = pos;
        return;
    }

    int mid = ( l + r ) / 2;

    update ( l, mid, idx * 2, pos, val );
    update ( mid + 1, r, idx * 2 + 1, pos, val );

    if ( -q[ it[idx * 2] ].top() > -q[ it[idx * 2 + 1] ].top() )
        it[idx] = it[idx * 2];
    else it[idx] = it[idx * 2  + 1];
}
void update ( int idx, int val ){
    update ( 1, N, 1, idx, val );
}

int query(){
    int idx = it[1], res;
    res = -q[idx].top();
    q[idx].pop();

    update ( idx, -q[idx].top() );

    return res;
}

void update(){
    int T, W;

    cin >> T >> W;
    q[T].push ( -W );

    update ( T, -q[T].top() );
}

void solve(){
    q[0].push ( 0 );
    for ( int i = 0; i < N; ++i ){
        int Q;

        cin >> Q;

        if ( Q == 2 )
            cout << query() << endl;
        else
            update();
    }
}
int main(){
    cin.tie(NULL);
    scan();
    solve();
}
