#include <cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int it[3][8000001];
struct so
{
    int c;
    int k;
    int i;
    int si;
};
bool cmp(so a,so b)
{
    return a.c<b.c;
}
bool cmp2(so a,so b)
{
    return a.i<b.i;
}
so a[200001];
bool pv(int x)
{
    if(it[1][x*2]==it[1][x*2+1])return (it[0][x*2]<it[0][x*2+1]);
    else return (it[0][x*2]>it[0][x*2+1]);
}
void update(int x,int l,int r,int p,int i)
{
    if(l==r)
    {
        it[0][x]=a[i].k;
        it[1][x]=a[i].c;
        return;
    }
    if(p<=(l+r)/2)update(x*2,l,(l+r)/2,p,i);
    else update(x*2+1,(l+r)/2+1,r,p,i);
    if(pv(x))
    {
        it[0][x]=it[0][x*2];
        it[1][x]=it[1][x*2];
    }
    else
    {
        it[0][x]=it[0][x*2+1];
        it[1][x]=it[1][x*2+1];
    }
}
void up2(int x,int l,int r)
{
    if(l==r)
    {
        it[0][x]=0;
        it[1][x]=0;
        return;
    }
    if(it[0][x*2]==it[0][x])up2(x*2,l,(l+r)/2);
    else up2(x*2+1,(l+r)/2,r);
    if(pv(x))
    {
        it[0][x]=it[0][x*2];
        it[1][x]=it[1][x*2];
    }
    else
    {
        it[0][x]=it[0][x*2+1];
        it[1][x]=it[1][x*2+1];
    }
}
void outtree(int x,int l,int r)
{
    printf("%d %d %d %d\n",l,r,it[0][x],it[1][x]);
    if(l==r)return;
    outtree(x*2,l,(l+r)/2);
    outtree(x*2+1,(l+r)/2+1,r);
}
int n,m;
vector<int>v[200004];
void solve()
{
    int ma,cm,i,j,x,k,a,b,c;
    for(i=0;i<n;i++)
    {
        cin>>x;
        if(x==2)
        {
            ma=0;
            for(j=1;j<=m;j++){
            cm=v[j][0];
            c=0;
            for(k=1;k<v[j].size();k++)
            if(cm>v[j][k])cm=v[j][k],c=k;
            if(j==0 || cm>ma)ma=cm,a=j,b=c;
            }
            v[a][b]=1000000000;
            cout<<ma<<endl;
        }
        else
        {
            cin>>a>>b;
            v[a].push_back(b);
        }
    }
}
int main()
{
    int f[2000001],p=0,i;
    scanf("%d%d",&n,&m);
    if(n<=5000)
    {
        solve();
        return 0;
        }
    for(i=0;i<n;i++)
    {
        scanf("%d",&f[p]);
        if(f[p]==1)
        {
            scanf("%d%d",&a[i-p].c,&a[i-p].k);
            a[i-p].i=i;
        }
        else
        {
            f[p]=i;
            p++;
        }
    }
    sort(a,a+(n-p),cmp);
    for(i=0;i<(n-p);i++)
    a[i].si=i;
    sort(a,a+(n-p),cmp2);
    int j=0;
    for(i=0;i<p;i++){
    for(j;j<n-p;j++)
    {
        if(f[i]<a[j].i)
        {
        //outtree(1,1,n-p);
           printf("%d\n",it[0][1]);
            up2(1,1,n-p);
            break;
        }
        update(1,1,n-p,a[j].si+1,j);
        //printf("%d %d %d %d\n",a[i].i,a[i].si,a[i].k,a[i].c);
    }
    if(n-p==j)break;}
    for(i;i<p;i++)
    {
        printf("%d\n",it[0][1]);
        up2(1,1,n-p);
    }
}
