#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
typedef long long Int;

struct hp
{
    Int ver,val;
};

priority_queue<Int> stones[200001];
hp MyHeap[1000001];
Int whereis[1000001];

void Update(Int ind)
{
    Int dad;
    hp help;
    Int d;

    dad=ind/2;

    while(dad>0)
    {
        if (MyHeap[dad].val<MyHeap[ind].val)
        {
            d=whereis[ MyHeap[ind].ver ];
            whereis[ MyHeap[ind].ver ]=whereis[ MyHeap[dad].ver ];
            whereis[ MyHeap[dad].ver ]=d;

            help=MyHeap[dad];
            MyHeap[dad]=MyHeap[ind];
            MyHeap[ind]=help;

            ind=dad;
            dad=ind/2;
        }
        else
        break;
    }

    return;
}

void Remove(Int dad)
{
    Int son1,son2;
    Int d;
    hp help;

    MyHeap[dad].val=-1;

    while(dad<500000)
    {
        son1=dad*2;
        son2=dad*2+1;

        if (MyHeap[son1].val>MyHeap[son2].val)
        {
            d=whereis[ MyHeap[son1].ver ];
            whereis[ MyHeap[son1].ver ]=whereis[ MyHeap[dad].ver ];
            whereis[ MyHeap[dad].ver ]=d;

            help=MyHeap[son1];
            MyHeap[son1]=MyHeap[dad];
            MyHeap[dad]=help;

            dad=son1;
        }
        else
        {
            d=whereis[ MyHeap[son2].ver ];
            whereis[ MyHeap[son2].ver ]=whereis[ MyHeap[dad].ver ];
            whereis[ MyHeap[dad].ver ]=d;

            help=MyHeap[son2];
            MyHeap[son2]=MyHeap[dad];
            MyHeap[dad]=help;

            dad=son2;
        }
    }

    return;
}

int main()
{
    Int n,m;
    Int i,j;
    Int command;
    Int t,w;
    Int toadd;
    Int thever;

    scanf("%lld %lld",&n,&m);

    for (i=0;i<=1000000;i++)
    {
        whereis[i]=i;
        MyHeap[i].val=-1;
        MyHeap[i].ver=i;
    }

    for (i=1;i<=n;i++)
    {
        scanf("%lld",&command);

        if (command==1)
        {
            scanf("%lld %lld",&t,&w);

            w=w*-1;

            stones[t].push(w);

            Remove(whereis[t]);

            MyHeap[ whereis[t] ].val=stones[t].top()*-1;

            Update(whereis[t]);
        }
        else
        {
            printf("%lld\n",MyHeap[1].val);

            thever=MyHeap[1].ver;

            stones[ MyHeap[1].ver ].pop();

            if (!stones[MyHeap[1].ver].empty())
            {
                MyHeap[1].val=stones[MyHeap[1].ver].top()*-1;
            }
            else
            {
                Remove(1);
            }
        }
    }

    return 0;
}
