#include<cstdio>
#include<algorithm>
using namespace std;
int m,m1,im1,n,o,x,y,a[8][200200],b[5050][5050],i1[5050];
bool fh(int a1,int a2)
{
    return a1>a2;
}
int main()
{
    int i;
    scanf("%d%d",&n,&m);
    if(m>5000){return -1;}
    if(m<6)
    {
            while(n>0)
            {
                --n;
                scanf("%d",&o);
                if(o==1)
                {
                    scanf("%d%d",&x,&y);
                    a[x][i1[x]]=y;
                    ++i1[x];
                    push_heap(a[x],a[x]+i1[x],fh);
                    //printf("%d\n",a[x][0]);
                }
                if(o==2)
                {
                    m1=0;
                    //printf("%d %d\n",a[0][0],a[1][0]);
                    for(i=1;i<=m;++i){if(a[i][0]>m1){m1=a[i][0];im1=i;}}
                    pop_heap(a[im1],a[im1]+i1[im1],fh);
                    --i1[im1];
                    printf("%d\n",m1);
                }
            }
            return 0;
    }
    while(n>0)
    {
        --n;
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d%d",&x,&y);
            b[x][i1[x]]=y;
            ++i1[x];
            push_heap(b[x],b[x]+i1[x],fh);
            //printf("%d\n",b[x][0]);
        }
        if(o==2)
        {
            m1=0;
            //printf("%d %d\n",b[0][0],b[1][0]);
            for(i=1;i<=m;++i){if(b[i][0]>m1){m1=b[i][0];im1=i;}}
            pop_heap(b[im1],b[im1]+i1[im1],fh);
            --i1[im1];
            printf("%d\n",m1);
        }
    }
    return 0;
}
