#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* a1, Nod* a2) {
        if (a1->val < a2->val) {
            Nod* temp = a1;
            a1 = a2;
            a2 = temp;
        }
        a1->nr_copii++;
        a2->parinte = a1;
        a2->frate = a1->copil;
        a1->copil = a2;
        return a1;
    }

    /* ///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)


     }*/

    ///pastram ordinea crescatoare a cheilor arborilor binomiali si pe cei cu nr de copii egal ii reunim

    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;
            anterior = arbori.begin();
            crnt = anterior;
            crnt++;
            urmator = crnt;
            urmator++;

            while(crnt!=arbori.end())
            {
                if(urmator!=arbori.end())
                {
                    if((*anterior)->nr_copii==(*crnt)->nr_copii && (*crnt)->nr_copii!=(*urmator)->nr_copii)
                    {
                        *anterior= reuniune_arbori(*anterior,*crnt);
                        crnt=arbori.erase(crnt);
                        urmator++;
                    }
                    else
                    {
                        anterior++;
                        crnt++;
                        urmator++;
                    }
                }
                else
                {
                    if((*anterior)->nr_copii==(*crnt)->nr_copii)
                    {
                        *anterior= reuniune_arbori(*anterior,*crnt);
                        arbori.pop_back();
                    }

                    crnt=arbori.end();
                }
            }
    }
};

    ///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;
}