#include <iostream>
#include <queue>
std::priority_queue<int, std::vector<int>, std::greater<int> > perTown[1<<18];
std::priority_queue<std::pair<int, std::size_t> > total;
std::size_t inTotalPerTown[1<<18];
void fall(std::size_t in, int mass){
    if(perTown[in].empty()||mass<perTown[in].top()){
        total.push(std::make_pair(mass, in));
        inTotalPerTown[in]++;
    }
    perTown[in].push(mass);
    return;
}
int tax(){
    while(total.top().first!=perTown[total.top().second].top()){
        inTotalPerTown[total.top().second]--;
        total.pop();
    }
    int mass=total.top().first;
    std::size_t town=total.top().second;
    perTown[town].pop();
    inTotalPerTown[town]--;
    total.pop();
    if(!perTown[town].empty()){
        inTotalPerTown[town]--;
        total.push(std::make_pair(perTown[town].top(), town));
    }
    return mass;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::size_t n, m;
    std::cin>>n>>m;
    for(std::size_t i=0;i<n;i++){
        std::size_t q;
        std::cin>>q;
        if(q==1){
            std::size_t town;
            int mass;
            std::cin>>town>>mass;
            fall(town, mass);
        }else{
            std::cout<<tax()<<'\n';
        }
    }
    return 0;
}
