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

ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

struct nod 
{

    int cheie, ordin;
    nod *copilStanga, *frateDreapta, *tata;  
    /// tata e intuitiv, 
    /// frateDreapta = fratele din dreapta al unui nod (frati sunt daca au acelasi tata)
    /// copilStanga = fiul cel mai din stanga al nodului
    /// pt a "traversa" fii unui nod mergi pe copil si apoi pe frati pana nu mai sunt
 
};

nod* nodNou (int cheie)
{
    nod* aux = new nod;
    aux->cheie = cheie;
    aux->ordin = 0;
    aux->copilStanga = NULL;
    aux->frateDreapta = NULL;
    aux->tata = NULL;

    return aux;
}

list <nod*> reunesteHeapuri(list <nod*> Heap1, list <nod*> Heap2)
{
    /// interclasare a arborilor dupa ordin si apoi un adjust => log n
    list <nod*> HeapNou;
    auto itHeap1 = Heap1.begin();
    auto itHeap2 = Heap2.begin();

    while (itHeap1 != Heap1.end() && itHeap2 != Heap2.end())
    {
        if ((*itHeap1)->ordin <= (*itHeap2)->ordin)
        {
            HeapNou.push_back(*itHeap1);
            itHeap1++;
        }
        else
        {
            HeapNou.push_back(*itHeap2);
            itHeap2++;
        }
    }
    while(itHeap1 != Heap1.end())
    {
        HeapNou.push_back(*itHeap1);
        itHeap1++;
    }
    while(itHeap2 != Heap2.end())
    {
        HeapNou.push_back(*itHeap2);
        itHeap2++;
    }
    Heap1.clear();
    Heap2.clear();
    return HeapNou;

}

void afisareArbore(list <nod*> Heap, nod* curent)
{
    cout << curent->cheie << " ";
    if (curent->frateDreapta != NULL)
    {
        afisareArbore(Heap, curent->frateDreapta);
    }
    if (curent->copilStanga != NULL)
    {
        afisareArbore(Heap, curent->copilStanga);
    }
}

void afisareArbore2(list <nod*> Heap, nod* curent)
{
    while (curent)
    {
        cout << curent->cheie << " ";
        afisareArbore2(Heap, curent->copilStanga);
        curent = curent->frateDreapta;
    }
}

void afisareHeap(list <nod*> Heap)
{
    auto itAfisare = Heap.begin();
    for (int i = 1; i <= Heap.size(); i++)
    {
        cout << "Arborele " << i << ": ";
        afisareArbore(Heap, *itAfisare);
        itAfisare++;
        cout << endl;
    }
}



struct HeapBinomial 
{

    list <nod*> Heap;

    nod* reunesteArbori(nod* arbore1, nod* arbore2)
    {
        if (arbore1->cheie < arbore2->cheie)
        {
            swap(*arbore1, *arbore2);
        }
        arbore2->tata = arbore1;
        arbore2->frateDreapta = arbore1->copilStanga;
        arbore1->copilStanga = arbore2;
        arbore1->ordin++;

        return arbore1;
    }

    void ajustare()
    {
        if (Heap.size() <= 1)
        {
            return;
        }
        else if (Heap.size() == 2)
        {
            if (Heap.front()->ordin == Heap.back()->ordin)
            {
                Heap.front() = reunesteArbori(Heap.front(), Heap.back());
                Heap.pop_back();
            }
            return ;
        }
        list <nod*>::iterator precedent, actual, urmator;
        precedent = Heap.begin();
        actual = precedent;
        actual++;
        urmator = actual;
        urmator++;
        while (precedent != Heap.end())
        {
            if (actual == Heap.end())
            {
                precedent++;
            }
            else if ((*precedent)->ordin < (*actual)->ordin)
            {
                precedent++;
                actual++;
                if (urmator != Heap.end())
                {
                    urmator++;
                }
            }
            else if (urmator != Heap.end() && (*precedent)->ordin == (*actual)->ordin && (*actual)->ordin == (*urmator)->ordin)
            {
                precedent++;
                actual++;
                urmator++;
            }
            else if ((*precedent)->ordin == (*actual)->ordin)
            {
                nod* aux;
                *precedent = reunesteArbori(*precedent, *actual);
                actual = Heap.erase(actual);
                if (urmator != Heap.end())
                {
                    urmator++;
                }
            }
        }

    }

    void inserare (int cheie)
    {
        nod* nou = nodNou(cheie);
        Heap.push_front(nou);
        ajustare();
    }

    void extragereMaxim()
    {

        /// afiszei radacina
        /// pt a extrage minimul trebuie sa faci un heap binomial format din toti copiii radacinii
        /// stergi radacina
        /// faci reuniune intre heap ul vechi si heap ul nou (teoretic daca stergi radacina ar trebui sa se stearga si din heap ul vechi si asa poti sa faci reuniunea linistit)
        int maxim = -1;
        auto itHeap = Heap.begin();
        auto itPozitieMaxim = Heap.begin();
        for (int i = 0; i < Heap.size(); i++)
        {
            if ((*itHeap)->cheie > maxim)
            {
                maxim = (*itHeap)->cheie;
                itPozitieMaxim = itHeap;
            }
            itHeap++;
        }
        nod* radacinaArboreMaxim = *(itPozitieMaxim);
        fout << maxim << endl;
        list <nod*> HeapNou;
        nod* nodAux = radacinaArboreMaxim->copilStanga;
        nod* nodFrate;
        while (nodAux != NULL)
        {
            nodAux->tata = NULL;
            nodFrate = nodAux->frateDreapta;
            nodAux->frateDreapta = NULL;
            HeapNou.push_front(nodAux);
            nodAux = nodFrate;
        }
        Heap.erase(itPozitieMaxim); /// pana aici totul merge perfect, deci problema e la reuniunea heap urilor
        Heap = reunesteHeapuri(Heap, HeapNou); /// aici practic la Heap reunim HeapNou, adica fix operatia 3 de pe infoarena, heap nou ar trebui sa ramana gol
        afisareHeap(HeapNou);
        ajustare();

    }

};

int main()
{
    int nrMultimi, nrOperatii;
    HeapBinomial VectorHeap[101];
    fin >> nrMultimi >> nrOperatii;
    int tipOperatie, indexHeap, elementInserare, indexHeap1, indexHeap2;
    for (int i = 1; i < nrOperatii; i++)
    {
        fin >> tipOperatie;
        if (tipOperatie == 1)
        {
            fin >> indexHeap >> elementInserare;
            VectorHeap[indexHeap].inserare(elementInserare);
        }
        else if (tipOperatie == 2)
        {
            fin >> indexHeap;
            VectorHeap[indexHeap].extragereMaxim();
        }
        else if (tipOperatie == 3)
        {
            fin >> indexHeap1 >> indexHeap2;
            VectorHeap[indexHeap1].Heap = reunesteHeapuri(VectorHeap[indexHeap1].Heap, VectorHeap[indexHeap2].Heap);
        }
    }
    return 0;
}

//    HeapBinomial test;
//
//    test.inserare(9);
//    test.inserare(3);
//    test.inserare(5);
//    test.inserare(1);
//    test.inserare(2);
//    test.inserare(8);
//    test.inserare(15);
//    test.inserare(11);
//    test.inserare(10);
//    test.inserare(6);
//    test.inserare(7);
//    test.inserare(4);
//    test.inserare(13);
//    test.inserare(14);
//    test.inserare(12);
//
//    afisareHeap(test.Heap);
//
//    test.extragereMaxim();
//    cout << endl;