#include<cstdio>
#include<queue>
using namespace std;
struct tree
{
    long long x,y;
};
struct idiot
{
    long long x;
    bool operator<(const idiot&gg)const
    {
        return gg.x<x;
    }
};
tree itree[3003003];
long long n,m,leaf[1001001];
priority_queue<idiot> q[1001001];
void read()
{
    scanf("%lld%lld",&n,&m);
}
void makeTree(int k,int l,int r)
{
    if(l==r)
    {
        leaf[l]=k;
        return;
    }
    makeTree(k*2,l,(l+r)/2);
    makeTree(k*2+1,(l+r)/2+1,r);
}
void solve()
{
    long long i,t,x,y,ind,ans;
    idiot g,gg;
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&t);
        if(t==1)
        {
            scanf("%lld%lld",&x,&y);
            gg.x=y;
            q[x].push(gg);
            g=q[x].top();
            ind=leaf[x];
            itree[ind].x=g.x;
            itree[ind].y=x;
            ind/=2;
            while(ind)
            {
                if(itree[ind*2].x>itree[ind*2+1].x)itree[ind]=itree[ind*2];
                else itree[ind]=itree[ind*2+1];
                ind/=2;
            }
        }
        else
        {
            ans=itree[1].x;
            printf("%lld\n",ans);
            q[itree[1].y].pop();
            g=q[itree[1].y].top();
            ind=leaf[itree[1].y];
            itree[ind].x=g.x;
            ind/=2;
            while(ind)
            {
                if(itree[ind*2].x>itree[ind*2+1].x)itree[ind]=itree[ind*2];
                else itree[ind]=itree[ind*2+1];
                ind/=2;
            }
        }
    }
}
int main()
{
    read();
    makeTree(1,1,m);
    solve();
}
/*
9 2
1 1 9
1 2 3
1 1 4
2
1 1 2
1 2 5
2
2
1 2 1
*/
