#include <iostream>
#include <fstream>
#include <vector>

///#include "pairing_heap.h"
///#include "binomial_heap.h"
///#include "leftist_heap.h"
using namespace std;

class leftist_heap;

struct node_leftist_heap{
    int key;
    int dist;
    node_leftist_heap *stanga, *dreapta;

    node_leftist_heap(int X, int Y) : key(X), dist(Y), stanga(NULL), dreapta(NULL){}
};

class leftist_heap{
    private:
        node_leftist_heap *root;

        node_leftist_heap* merge_heap(node_leftist_heap* A, node_leftist_heap* B){
            ///A <- B
            if(A == NULL){
                return B;
            }
            if(B == NULL){
                return A;
            }

            if( (B->key) > (A->key) ){
                swap(A, B);
            }

            if(A->stanga == NULL){
                A->stanga = B;
            }
            else {
                A->dreapta = merge_heap(A->dreapta, B);

                if( (A->dreapta->dist) > (A->stanga->dist) ){
                    swap(A->stanga, A->dreapta);
                }
                A->dist = 1 + (A->dreapta->dist);

            }

            return A;
        }


    public:
        leftist_heap() : root(NULL) {}

        leftist_heap (int key, int dist){
            root = new node_leftist_heap(key, dist);
        }

        void heap_union (leftist_heap &H){
            root = merge_heap(root, H.root);
            H.root = NULL;
        }
        int top(){
            return root -> key;
        }
        void push(int key){
            root = merge_heap( root, leftist_heap(key, 0).root );
        }
        void pop(){
            node_leftist_heap *temp = root;
            root = merge_heap(root -> stanga, root -> dreapta);
            delete temp;
        }
};



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

    int N, M;
    fin >> N >> M;


    ///vector< pairing_heap > list_of_pairing_heap;
    ///vector< binomial_heap > list_of_binomial_heap;
    vector< leftist_heap > list_of_leftist_heap;
    for(int i = 0; i <= N; i++){
        ///pairing_heap temp;
        ///list_of_pairing_heap.push_back(temp);

        ///binomial_heap temp;
        ///list_of_binomial_heap.push_back(temp);

        leftist_heap temp;
        list_of_leftist_heap.push_back(temp);
    }

    int task, h, x, h1, h2;
    for( int i = 1; i <= M; ++i ){
        fin >> task;

        if( task == 1 ){
            fin >> h >> x;

            ///list_of_pairing_heap[h].push( x );
            ///list_of_binomial_heap[h].push( x );
            list_of_leftist_heap[h].push( x );
        }
        if( task == 2 ){
            fin >> h;

            ///fout << list_of_pairing_heap[h].top() << '\n';
            ///list_of_pairing_heap[h].pop();

            ///fout << list_of_binomial_heap[h].top() << '\n';
            ///list_of_binomial_heap[h].pop();

            fout << list_of_leftist_heap[h].top() << '\n';
            list_of_leftist_heap[h].pop();
        }
        if( task == 3 ){
            fin >> h1 >> h2;

            ///list_of_pairing_heap[h1].heap_union( list_of_pairing_heap[h2] );
            ///list_of_binomial_heap[h1].heap_union( list_of_binomial_heap[h2] );
            list_of_leftist_heap[h1].heap_union( list_of_leftist_heap[h2] );
        }
    }

    return 0;
}