#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;

ifstream fin("abce.in");
ofstream fout("abce.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();
    temp->left = temp->right = NULL;
    return temp;
}

TreapNode* search(TreapNode* root, int key) {
    if (!root || root->key == key) return root;
    if (key < root->key) return search(root->left, key);
    return search(root->right, key);
}

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 {
        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 {
        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) {
            root = leftRotate(root);
            root->left = deleteNode(root->left, key);
        } else {
            root = rightRotate(root);
            root->right = deleteNode(root->right, key);
        }
    }
    return root;
}

int findMaxLE(TreapNode* root, int x) {
    int res = -1e9 - 5;
    while (root) {
        if (root->key <= x) {
            res = root->key;
            root = root->right;
        } else {
            root = root->left;
        }
    }
    return res;
}

int findMinGE(TreapNode* root, int x) {
    int res = 1e9 + 5;
    while (root) {
        if (root->key >= x) {
            res = root->key;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return res;
}

void rangeQuery(TreapNode* root, int x, int y, vector<int>& result) {
    if (!root) return;
    if (x < root->key)
        rangeQuery(root->left, x, y, result);
    if (x <= root->key && root->key <= y)
        result.push_back(root->key);
    if (y > root->key)
        rangeQuery(root->right, x, y, result);
}

// Function to find the maximum element in the Treap
int getMaxElement(TreapNode* root) {
    if (!root) return -1e9 - 5; // Consistent with findMaxLE for empty/not found
    while (root->right) {
        root = root->right;
    }
    return root->key;
}

// Function to merge two Treaps t1 and t2
// Assumes max_key(t1) < min_key(t2) to maintain BST property.
TreapNode* mergeTreaps(TreapNode* t1, TreapNode* t2) {
    if (!t1) return t2;
    if (!t2) return t1;

    if (t1->priority > t2->priority) {
        t1->right = mergeTreaps(t1->right, t2);
        return t1;
    } else {
        t2->left = mergeTreaps(t1, t2->left);
        return t2;
    }
}

int main() {
    srand(time(0)); // pentru randomizarea priorităților în Treap

    int N, Q;
    fin >> N >> Q;

    vector<TreapNode*> heap(N + 1, nullptr);

    for (int i = 0; i < Q; ++i) {
        int op;
        fin >> op;
        if (op == 1) {
            int m, x;
            fin >> m >> x;
            heap[m] = insert(heap[m], x);
        } else if (op == 2) {
            int m;
            fin >> m; // Adaugă această linie
            int maxVal = getMaxElement(heap[m]);
            fout << maxVal << '\n';
            heap[m] = deleteNode(heap[m], maxVal);
        } else if (op == 3) {
            int a, b;
            fin >> a >> b;
            if (a == b) continue;

            // Important: trebuie să ne asigurăm că toate cheile din a < toate cheile din b
            // DAR în problemă nu avem o astfel de garanție, deci trebuie să folosim split + merge custom
            // Așadar, în loc să ne bazăm pe BST property, ignorăm această restricție și reunim fără ordine
            // Soluția: inserăm elementele din b în a (eficient dacă b este mic) => evităm pentru Q mare

            // Mai bine: adaptăm mergeTreaps ca să NU presupună disjuncția valorică
            // Și o folosim direct:
            heap[a] = mergeTreaps(heap[a], heap[b]);
            heap[b] = nullptr;
        }
    }

    fin.close();
    fout.close();
    return 0;
}