#include <iostream>
#include <vector>
#include <list>
#include <fstream>
using namespace std;

ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

struct Nod
{
    int val, nr_copii;
    Nod* parinte;
    Nod* copil;
    Nod* frate;

};

Nod* nod_nou(int valoare)
{
    Nod* nou= new Nod;
    nou->val=valoare;
    nou->parinte=nou->copil=nou->frate=nullptr;
    nou->nr_copii=0;
    return nou;
}

struct HeapBionomial
{
    list<Nod*> arbori;
    ///reunim arborii-arborele cu val mai mica va fi parintele(radacina) arborelui cu val mai mare(va fi adăugat ca un subarbore al rădăcinii)

    Nod* reuniune_arbori(Nod* arbore1, Nod* arbore2)
    {
    if (arbore1->val<arbore2->val) {
        swap(*arbore1, *arbore2);
    }

    arbore2->parinte=arbore1;
    arbore2->frate=arbore1->copil;
    arbore1->copil=arbore2;
    arbore1->nr_copii++;
        return arbore1;
    }

   /* ///creare lista arbori
    void creareArbori(Nod* heap1, Nod* heap2)
    {
        Nod* curent=heap1;
        while(curent!=nullptr)
        {
            arbori.push_front(curent);
            curent=curent->frate;
        }

        curent=heap2;
        while(curent!=nullptr)
        {
            arbori.push_front(curent);
            curent=curent->frate;
        }

        arbori.sort([](Nod* a, Nod* b) {return a->val< b->val;});   ///am sortat arborii crescator dupa cheie(val)


    }*/

    ///reuniune heap-uri binomiale pastrand ordinea crescatoare a cheilor arborilor binomiali

    void modif_lista_arbori()
    {
        arbori.sort([](Nod* a, Nod* b) { return a->nr_copii < b->nr_copii; });
        ///facem o lista cu toti arborii din cele 2 heap uri in ordine cresc a valorilor
        if (arbori.size()<=1)
        {
            return ;
        }
        else if (arbori.size()==2)
        {
            if (arbori.front()->nr_copii==arbori.back()->nr_copii)
            {
                arbori.front()=reuniune_arbori(arbori.front(), arbori.back());
                arbori.pop_back();
            }
            arbori.sort([](Nod* a, Nod* b) { return a->nr_copii < b->nr_copii; });
            return;
        }

        else {

            list<Nod *>::iterator anterior;
            list<Nod *>::iterator crnt;
            list<Nod *>::iterator urmator;
            list <Nod* > :: iterator temp;
            anterior = arbori.begin();
            crnt = anterior;
            crnt++;
            urmator = crnt;
            urmator++;

            while( crnt != arbori.end() ){

                while ( ( urmator == arbori.end() || (*urmator) -> nr_copii > (*crnt) -> nr_copii ) && crnt != arbori.end() && (*anterior) -> nr_copii == (*crnt) -> nr_copii ){

                    reuniune_arbori( *crnt, *anterior );

                    temp = anterior;

                    if(anterior== arbori.begin() ){
                        anterior++;
                        crnt++;
                        if( urmator != arbori.end() )
                            urmator++;
                    }
                    else anterior--;

                    arbori.erase( temp );

                }

                anterior++;
                if(crnt!= arbori.end() ) crnt++;
                if( urmator!= arbori.end() ) urmator++;
            }

        }

    }

    ///reunim heapuri

    void reuniune_heap(HeapBionomial& heap2)
    {
        list<Nod*> HeapFinal;
        list<Nod*> :: iterator a1, a2;
        a1=arbori.begin();
        a2= heap2.arbori.begin();

        while(a1!=arbori.end() && a2!=heap2.arbori.end())
        {
            if((*a2)->nr_copii>=(*a1)->nr_copii)
            {
                HeapFinal.push_front(*a1);
                a1++;
            }
            else
            {
                HeapFinal.push_front(*a2);
                a2++;
            }
            while (a1!=arbori.end())
            {
                HeapFinal.push_front(*a1);
                a1++;
            }

            while (a2!=heap2.arbori.end())
            {
                HeapFinal.push_front(*a2);
                a2++;
            }
        }

        heap2.arbori.clear();
        arbori=HeapFinal;
        modif_lista_arbori();

    }

    /// inseram un nod nou in heap
    void inserare_val(int valoare)
    {
        Nod* nou=nod_nou(valoare);
        arbori.push_back(nou);
        modif_lista_arbori();
    }

    ///gasim radacina cu valoarea maxima si o eliminam

    void eliminare()
    {
        if (arbori.empty()) {
            return ;
        }

        auto it = arbori.begin();
        Nod* max = *it;
        while (it != arbori.end()) {
            if ((*it)->val > max->val) {
                max= *it;
            }
            it++;
        }

        arbori.remove(max);
        list<Nod*> subarbori;
        Nod* sa=max->copil;
        g<<(*max).val<<endl;
        while (sa!=NULL)
        {
            subarbori.push_front(sa);
            sa=sa->frate;
        }

        auto it2 = subarbori.begin();
        while (it2!= subarbori.end())
        {
            arbori.push_back(*it2);
            it2++;
        }
        modif_lista_arbori();
    }

};

int main()
{
    int mult,op;
    f>>mult >>op;
    HeapBionomial Heap[101];
    int nrOp, it, valoare, i1, i2;
    for (int i = 1; i <=op; i++) {
        f >> nrOp;
        if (nrOp == 1) {
            f >> it;
            f >> valoare;
            Heap[it].inserare_val(valoare);

        } else if (nrOp == 2) {
            f >> it;
            Heap[it].eliminare();
        } else if (nrOp == 3) {
            f >> i1 >> i2;
            Heap[i1].reuniune_heap(Heap[i2]);
        }
    }
    return 0;
}