#include <bits/stdc++.h>
#include <malloc.h>
using namespace std;

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

//https://www.geeksforgeeks.org/fibonacci-heap-insertion-and-union/
/*
1) Find Max:      Θ(1)     [Same as both Binary and Binomial]
2) Delete Max:    O(Log n) [Θ(Log n) in both Binary and Binomial]
3) Insert:        Θ(1)     [Θ(Log n) in Binary and Θ(1) in Binomial]
4) Decrease-Key:  Θ(1)     [Θ(Log n) in both Binary and Binomial]
5) Merge:         Θ(1)     [Θ(m Log n) or Θ(m+n) in Binary and Θ(Log n) in Binomial]
*/

//https://infoarena.ro/problema/mergeheap + BUILD în O(n) din n elemente!
//Insert, delete min, build, merge


struct nod
{
    nod* parent;
    nod* child;
    nod* left;
    nod* right;
    int val;
    int degree;
};

///initilize max
///double linked list, so if we know the maxi, we can access any node in the tree
nod* maxi[105];
nod* v[105];     ///pointer for each tree

int n, q;
///nr nodes in  each heap
int sz_heap[105];


///insertion
void insertion(int val, int t)      ///insert val in tree t
{
    ///create a new node

    //http://www.cplusplus.com/reference/cstdlib/malloc/
    //locates a block of size bytes of memory, returning a pointer to the beginning of the block.
    //The content of the newly allocated block of memory is not initialized, remaining with indeterminate values.
    nod* newn = (nod*)malloc(sizeof(nod));

    ///suppose it's the only one, it points at itself
    newn->val = val;
    newn->degree = 0;
    newn->parent = 0; //no childs
    newn->child = 0; //no parent
    newn->left = newn;
    newn->right = newn;


    if (maxi[t] != 0)
    {
        ///recreate the links
        ///INSERT NEAR THE MINI
        (maxi[t]->left)->right = newn;
        newn->right = maxi[t];
        newn->left = maxi[t]->left;
        maxi[t]->left = newn;

        if (val > maxi[t]->val)
            maxi[t] = newn;
    }
    else
    {
       maxi[t] = newn;
    }
    sz_heap[t]++;

}
/*
///kept sorted
void display(nod* maxi[t])
{
    nod *p = maxi[t];
    if(p == 0)
    {
        fout << "The heap is empty";
    }
    else
        {
            fout << "The root nodes of the heap: \n";
            do
            {
                fout << p->val;
                p = p->right;
                if(p != maxi[t])///we still have nodes
                {
                    fout << "-->";
                }
            }while(p != maxi[t] && p->right != 0);

        }
}
*/

///linking thea heap nodes in parent-child realtionship
///P1 > P2
void fibonacci_link(nod *p2, nod *p1, int t)
{
    ///extract them from the list --> we have to remake the link in:  o-o-p1-o-o-p2-o
    ///--> o-o--o-o--o

    (p2->left)->right = p2->right;
    (p2->right)->left = p2->left;


    if(p1->right == p1)
        maxi[t] = p1;
    p2->left = p2;
    p2->right = p2;///points to itself
    p2->parent = p1;

    ///      p1
    ///     / |
    ///    p2 o
    ///    |
    ///    o

    if(p1 ->child == NULL)
       p1->child = p2;
    p2->right = p1->child;      ///insert to the right of the child
    p2->left = (p1->child)->left;
    ((p1->child)->left)->right = p2;
    (p1->child)->left = p2;

    if(p2->val > (p1->child)->val)  ///keep pointer to the maxim child
        p1->child = p2;
    p1->degree++;

}
///consolodate trees so that no two roots have the same degree
void consolidate(int t)
{
    int temp1;
    float temp2 = (log(sz_heap[t])) / (log(2)); /// lg of the array where we keep the degrees
    int temp3 = temp2;
    nod* arr[temp3];
    int i;

    for(i = 0; i <= temp3; ++i)
        arr[i] = NULL;  ///we don't have any tree yet
    nod *p1 = maxi[t];
    nod *p2, *p3, *p4 = p1;

    do{                 ///for each node we union them till we still have trees with the same degree
        p4 = p4->right; ///start the union from the right
        temp1 = p1->degree;
        while(arr[temp1] != NULL)       ///search for trees with same degree
        {
            p2 = arr[temp1];
            if(p1->val < p2->val)       ///swap them            THE ORDER DESIRED: P1 > P2
            {
                p3 = p1;
                p1 = p2;
                p2 = p3;
            }

            if(p2 == maxi[t])          ///?????????????????????????
                maxi[t] = p1;

            fibonacci_link(p2, p1, t);     ///union the trees

            if(p1->right == p1)
                maxi[t] = p1;
            arr[temp1] = NULL;  ///there is not any tree with this degree anymore
            temp1++;    ///increase the degree
        }

        arr[temp1] = p1;       ///keep at that degree the new resulted tree
        p1 = p1->right;        ///move to the next tree;
    }while(p1 != maxi[t]);         /// we still have trees that we haven't union them yet
    maxi[t] = NULL;
    for(i = 0; i <= temp3; ++i)
    {
        if(arr[i] != NULL)      ///we have a tree with that degree
        {
            arr[i]->left = arr[i];      ///remake the duble liked list
            arr[i]->right = arr[i];     ///if it's the only root

            if(maxi[t] != NULL)        ///insert the tree near the maxi
            {
                (maxi[t]->left)->right = arr[i];
                arr[i]->right = maxi[t];
                arr[i]->left = maxi[t]->left;
                maxi[t]->left = arr[i];

                if(arr[i]->val > maxi[t]->val)     ///we know that the max is in the root of the tree
                    maxi[t] = arr[i];
            }
            else
            {
                maxi[t] = arr[i];
            }

            if(maxi[t] == NULL || arr[i]->val > maxi[t]->val)     ///the new max
                maxi[t] = arr[i];
        }
    }
}

void extract_max(int t)     ///from the tree t
{
    if(maxi[t] == NULL)
        fout << "The heap is empty\n";

    else
    {
        fout << maxi[t]->val << "\n";
        nod *temp = maxi[t];
        nod *p;
        p = temp;
        nod* x = NULL;
        if(temp -> child != NULL)
        {
            x = temp->child;
            do          ///remake the links
            {
                p = x->right;   ///keep the next node for which we will apply the algh
                (maxi[t]->left)->right = x;
                x->right = maxi[t];    ///duble linked list to the left element
                x->left = maxi[t]->left;
                maxi[t]->left = x;
                if(x->val > maxi[t]->val)
                    maxi[t] = x;
                x->parent = NULL; ///it s on the firt floor
                x = p;
            }while(p != temp ->child); ///till we still have to update nodes on that nivel
        }
        (temp->left)->right = temp->right;///remake the link in order to delete the "maxi"
        (temp->right)->left = temp->left;
        maxi[t] = temp->right;
        if(temp == temp->right && temp->child == 0) ///no more nodes in the heap
            maxi[t] = NULL;
        else
        {
            maxi[t] = temp->right;     ///the new maxi
            consolidate(t);      ///update the degrees

        }
        sz_heap[t]--;
    }
}
void merge_trees(int a, int b)  ///seems like fibonacci_link
{
    nod *p = maxi[b];

    do
    {
     insertion(p->val,a);
     p = p->right;
    }while(p != maxi[b] && p->right != 0);
    sz_heap[b] =0;
    maxi[b] = 0;




}
void initilise()
{
    int i;
    for(i = 1; i <= n; ++i)
        maxi[i] = NULL;
}
void read()
{
    int i, task, x, m;
    fin >> n >> q;
    initilise();
    for(i = 1; i <= q; ++i)
    {
        fin >> task;
        if(task == 1)
        {
            fin >> m >> x;
            insertion(x, m);

        }
        else if(task == 2)
        {
            fin >> m;
            extract_max(m);
        }
        else if(task == 3)
        {
            fin >> m >> x;
            merge_trees(m, x);

        }
    }

}
int main()
{
    read();

    return 0;
}