#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm> // For std::max if needed, though not directly for treap logic

using namespace std;

// Adjusted file streams
ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

struct TreapNode {
    int key, priority;
    TreapNode *left, *right;
};

TreapNode* rightRotate(TreapNode* y) {
    TreapNode *x = y->left;
    TreapNode *T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}

TreapNode* leftRotate(TreapNode* x) {
    TreapNode *y = x->right;
    TreapNode *T2 = y->left;
    y->left = x;
    x->right = T2;
    return y;
}

TreapNode* newNode(int key) {
    TreapNode* temp = new TreapNode;
    temp->key = key;
    temp->priority = rand(); // Standard random priority
    temp->left = temp->right = NULL;
    return temp;
}

TreapNode* insert(TreapNode* root, int key) {
    if (!root) return newNode(key);
    if (key < root->key) {
        root->left = insert(root->left, key);
        if (root->left->priority > root->priority)
            root = rightRotate(root);
    } else { // Allow duplicate keys by inserting to the right, or handle as per problem if duplicates are disallowed/special
        root->right = insert(root->right, key);
        if (root->right->priority > root->priority)
            root = leftRotate(root);
    }
    return root;
}

TreapNode* deleteNode(TreapNode* root, int key) {
    if (!root) return root;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else { // Key found
        if (!root->left) {
            TreapNode* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            TreapNode* temp = root->left;
            delete root;
            return temp;
        }
        if (root->left->priority < root->right->priority) { // If right child has higher priority
            root = leftRotate(root); // Rotate left, key to delete moves to left
            root->left = deleteNode(root->left, key);
        } else { // If left child has higher or equal priority
            root = rightRotate(root); // Rotate right, key to delete moves to right
            root->right = deleteNode(root->right, key);
        }
    }
    return root;
}

// Function to find the maximum element in the Treap
int getMaxElement(TreapNode* root) {
    if (!root) return -2e9 - 7; // Should not happen based on problem constraints for op 2
    while (root->right) {
        root = root->right;
    }
    return root->key;
}

// Helper function to collect all elements from a treap (pre-order traversal)
void collectElements(TreapNode* node, std::vector<int>& elements) {
    if (!node) return;
    elements.push_back(node->key);
    collectElements(node->left, elements);
    collectElements(node->right, elements);
}

// Helper function to delete all nodes in a treap and set its root to NULL
void deleteFullTreap(TreapNode*& node) {
    if (!node) return;
    deleteFullTreap(node->left);
    deleteFullTreap(node->right);
    delete node;
    node = NULL;
}

int main() {
    srand(time(NULL));

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

    std::vector<TreapNode*> heaps(N_sets + 1, NULL); // 1-indexed heaps

    for (int q_idx = 0; q_idx < Q_ops; ++q_idx) {
        int type;
        fin >> type;
        if (type == 1) {
            int m, x;
            fin >> m >> x;
            if (m >= 1 && m <= N_sets) {
                heaps[m] = insert(heaps[m], x);
            }
        } else if (type == 2) {
            int m;
            fin >> m;
            if (m >= 1 && m <= N_sets) {
                int max_val = getMaxElement(heaps[m]);
                fout << max_val << '\n';
                heaps[m] = deleteNode(heaps[m], max_val);
            }
        } else if (type == 3) {
            int a_idx, b_idx;
            fin >> a_idx >> b_idx;
            if (a_idx >= 1 && a_idx <= N_sets && b_idx >= 1 && b_idx <= N_sets && a_idx != b_idx) {
                if (heaps[b_idx] != NULL) {
                    std::vector<int> elements_from_b;
                    collectElements(heaps[b_idx], elements_from_b);
                    deleteFullTreap(heaps[b_idx]); // Empties treap b and frees memory

                    for (int val : elements_from_b) {
                        heaps[a_idx] = insert(heaps[a_idx], val);
                    }
                }
            }
        }
    }

    // Optional: Clean up memory for all treaps at the end
    for (int i = 1; i <= N_sets; ++i) {
        deleteFullTreap(heaps[i]);
    }

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

    return 0;
}