#include <iostream>
#include <cstdio>
#include <set>
#define MAX 0
using namespace std;
multiset<int> W[1<<18];
int n, m, it[1<<20], par[1<<20], k = 1;
int Top(){

}
void Insert(int num, int val){
    num += k;
    it[num] = val;
    par[num] = num - k;
    while(num > 1){
        num /=2;
        it[num] = max(it[num*2] , it[num*2+1]);
        if(it[num*2] >= it[num*2+1])
            par[num]= par[num*2];
        else par[num]= par[num*2+1];
    }
}
void Pop(int x){
    int p = MAX;
    printf("%d\n", *W[x].begin());
    W[x].erase(*W[x].begin());
    if(!W[x].empty()) p = *W[x].begin();
    Insert(x, p);
}
int main(){
    scanf("%d%d", &n, &m);
    while(k < m)
        k = (k<<1);
    k --;
    for(int i = k + k + 1; i >= 1; i--)
        Insert(i, MAX);
    //for(int i = 1; i <= k + k + 1; i++)
        //cout<<par[i]<<" "<<it[i]<<endl;
    for(; n > 0; n--){
        int op, num, val;
        scanf("%d", &op);
       // cout<<op<<endl;
        if(op == 2){
                //cout<<" "<<par[1]<<endl;
            Pop( par[1] );
        }
        else {
            scanf("%d%d", &num, &val);
            W[num].insert(val);
            if(*W[num].begin() == val) Insert(num, val);
        }
    }
    return 0;
}
