#include <iostream>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;

int n,m;
priority_queue<int, vector<int>, greater<int> > q[200001];

void slowsolve()
{
    int cmd, a, b, k, mx, cr;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &cmd);
        if(cmd==1)
        {
            scanf("%d%d", &a, &b);
            q[a].push(b);
        }
        else
        {
            mx=0;
            for(int i=1; i<=m; i++)
            {
                if(!q[i].empty())
                {
                    cr=q[i].top();
                    if(cr>mx){ k=i; mx=cr;}
                }
            }
            printf("%d\n", mx);
            q[k].pop();
        }
    }
}

struct stone
{
    int val, town;
    stone(){}
    stone(int x, int y)
    {
        val=x;
        town=y;
    }

    bool operator<(const stone &other)
    const{
        return val>other.val;
    }

    bool operator==(const stone &other)
    const {
        return val==other.val;
    }
};

set<stone> st;

void fastsolve()
{
    int cmd, a, b, k, mx,c;
    stone cr;
    set<stone>::iterator bg;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &cmd);
        if(cmd==1)
        {
            scanf("%d%d", &a, &b);
            if(!q[a].empty())
            {
                c=q[a].top();
                if(b<c)
                {
                    st.erase(stone(c,a));
                    st.insert(stone(b,a));
                    q[a].push(b);
                }
                else q[a].push(b);
            }
            else{
                    q[a].push(b);
                    st.insert(stone(b,a));
            }
        }
        else
        {
            bg=st.begin();
            cr=*bg;
            mx=cr.val;
            printf("%d\n", mx);
            a=cr.val; b=cr.town;
            st.erase(cr);
            q[b].pop();
            if(!q[b].empty()) st.insert(stone(q[b].top(),b));
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    if(n<=5000 || m<=5)
        fastsolve();
    else fastsolve();
}
