#include <cstdlib>
#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <algorithm> // Pentru std::swap

struct node {
    node * parent;
    node * child;
    node * left;
    node * right;
    int key; 
    int degree;
    char mark;
    // char c; // Neutilizat?
};

struct node* current_mini = NULL;
int current_no_of_nodes = 0;

void insertion_fib(int val) { 
    node * new_node = new node();
    new_node -> key = val;
    new_node -> parent = NULL;
    new_node -> child = NULL;
    new_node -> degree = 0;
    new_node -> mark = 'W'; 
    new_node -> left = new_node;
    new_node -> right = new_node;

    if(current_mini != NULL) {
        (current_mini->left)->right = new_node;
        new_node->right = current_mini;
        new_node->left = current_mini->left;
        current_mini->left = new_node;
        if (new_node->key < current_mini->key)
            current_mini = new_node;
    }
    else {
        current_mini = new_node;
    }
    current_no_of_nodes++;
}

node* merge_fib_lists(node* heap1_mini, node* heap2_mini) {
    if (heap1_mini == NULL) return heap2_mini;
    if (heap2_mini == NULL) return heap1_mini;

    node* heap1_left_orig = heap1_mini->left;
    node* heap2_left_orig = heap2_mini->left;

    heap1_left_orig->right = heap2_mini;
    heap2_mini->left = heap1_left_orig;

    heap2_left_orig->right = heap1_mini;
    heap1_mini->left = heap2_left_orig;

    if (heap2_mini->key < heap1_mini->key) {
        return heap2_mini;
    }
    return heap1_mini;
}


void Fibonnaci_link(struct node* ptr2, struct node* ptr1) { 
    (ptr2->left)->right = ptr2->right;
    (ptr2->right)->left = ptr2->left;

    ptr2->parent = ptr1;
    ptr2->mark = 'W'; 

    if (ptr1->child == NULL) {
        ptr1->child = ptr2;
        ptr2->left = ptr2; 
        ptr2->right = ptr2;
    } else {
        ptr2->left = (ptr1->child)->left;
        ptr2->right = ptr1->child;
        ((ptr1->child)->left)->right = ptr2;
        (ptr1->child)->left = ptr2;
    }
    ptr1->degree++;
}

void Consolidate() {
    if (current_mini == NULL) return;

    float temp2 = (log(static_cast<float>(current_no_of_nodes))) / (log(2.0f));
    int max_degree_approx = static_cast<int>(temp2) + 2; 
    std::vector<node*> degree_table(max_degree_approx, nullptr);

    std::vector<node*> root_list_nodes;
    if(current_mini) { // Asigură-te că current_mini nu e null înainte de a-l dereferenția
        node* temp_ptr = current_mini;
        do {
            root_list_nodes.push_back(temp_ptr);
            temp_ptr = temp_ptr->right;
        } while(temp_ptr != current_mini);
    }

    for(node* ptr1 : root_list_nodes) {
        if(ptr1 == nullptr) continue; // Adăugat pentru siguranță, deși nu ar trebui să se întâmple
        int d = ptr1->degree;
        while (d < degree_table.size() && degree_table[d] != NULL) { // Verifică limitele lui d
            node* ptr2 = degree_table[d]; 
            if (ptr1->key > ptr2->key) { 
                std::swap(ptr1, ptr2);
            }
            Fibonnaci_link(ptr2, ptr1); 
            degree_table[d] = NULL;
            d++;
             if(d >= degree_table.size()){ // Previne ieșirea din limite dacă gradul crește mult
                degree_table.resize(d + 2, nullptr);
            }
        }
        if(d < degree_table.size()){ // Verifică din nou limitele
             degree_table[d] = ptr1;
        } else { // Dacă d a depășit dimensiunea inițială
            degree_table.resize(d + 2, nullptr);
            degree_table[d] = ptr1;
        }
    }

    current_mini = NULL; 
    for (int i = 0; i < degree_table.size(); i++) {
        if (degree_table[i] != NULL) {
            node* current_node_from_table = degree_table[i];
            current_node_from_table->parent = NULL; 
            if (current_mini == NULL) {
                current_mini = current_node_from_table;
                current_mini->left = current_mini;
                current_mini->right = current_mini;
            } else {
                current_node_from_table->left = current_mini->left;
                current_node_from_table->right = current_mini;
                (current_mini->left)->right = current_node_from_table;
                current_mini->left = current_node_from_table;
                if (current_node_from_table->key < current_mini->key) {
                    current_mini = current_node_from_table;
                }
            }
        }
    }
}

bool Extract_min_fib(int& extracted_value) {
    if (current_mini == NULL) {
        return false;
    }

    node* z = current_mini;
    extracted_value = -(z->key); 

    if (z->child != NULL) {
        node* current_child = z->child;
        node* first_child = z->child; // Salvează primul copil pentru a detecta sfârșitul listei circulare
        std::vector<node*> children_to_add_to_root;
        
        // Colectează copiii într-un vector temporar pentru a evita problemele
        // la modificarea listei de rădăcini în timp ce o parcurgi pe cea de copii
        node* temp_child_ptr = first_child;
        do {
            children_to_add_to_root.push_back(temp_child_ptr);
            temp_child_ptr = temp_child_ptr->right;
        } while (temp_child_ptr != first_child);

        for(node* child_node : children_to_add_to_root) {
            // Adaugă child_node la lista de rădăcini
            child_node->left = current_mini->left;
            child_node->right = current_mini;
            (current_mini->left)->right = child_node;
            current_mini->left = child_node;
            child_node->parent = NULL; 
        }
    }

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

    if (z == z->right) { 
        current_mini = NULL;
    } else {
        current_mini = z->right; 
        Consolidate();         
    }
    current_no_of_nodes--;
    delete z; 
    return true;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    if (!fin.is_open()) {
        // std::cerr << "Eroare la deschiderea mergeheap.in" << std::endl;
        return 1;
    }
    if (!fout.is_open()) {
        // std::cerr << "Eroare la deschiderea mergeheap.out" << std::endl;
        return 1;
    }

    int N_sets, Q_ops;
    fin >> N_sets >> Q_ops;

    std::vector<node*> heap_min_pointers(N_sets + 1, nullptr); 
    std::vector<int> heap_node_counts(N_sets + 1, 0);    

    for (int i = 0; i < Q_ops; ++i) {
        int type;
        fin >> type;

        if (type == 1) {
            int m, x_original;
            fin >> m >> x_original;

            current_mini = heap_min_pointers[m];
            current_no_of_nodes = heap_node_counts[m];

            insertion_fib(-x_original); 

            heap_min_pointers[m] = current_mini;
            heap_node_counts[m] = current_no_of_nodes;

        } else if (type == 2) {
            int m;
            fin >> m;

            current_mini = heap_min_pointers[m];
            current_no_of_nodes = heap_node_counts[m];

            int extracted_original_value;
            if (Extract_min_fib(extracted_original_value)) {
                fout << extracted_original_value << "\n";
            }
            
            heap_min_pointers[m] = current_mini;
            heap_node_counts[m] = current_no_of_nodes;

        } else if (type == 3) {
            int a, b;
            fin >> a >> b;

            if (a == b) continue;
            if (heap_min_pointers[b] == nullptr) continue; // Nu e nimic de unit din heap-ul b

            heap_min_pointers[a] = merge_fib_lists(heap_min_pointers[a], heap_min_pointers[b]);
            heap_node_counts[a] += heap_node_counts[b];

            heap_min_pointers[b] = nullptr;
            heap_node_counts[b] = 0;
        }
    }

    fin.close();
    fout.close();

    // Eliberarea memoriei (omisa pentru concursuri de obicei)
    return 0;
}