#include <iostream>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <queue>
using namespace std;

const int NMAX = 105;

struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;  // Adăugat pointer către părinte
    int rank = 0;
};

class RankPairingHeap {
    Node* root = nullptr;

public:
    RankPairingHeap() {}
    ~RankPairingHeap() {}

    Node* getRoot() const {
        return root;
    }

    void setRoot() {
        root = nullptr;
    }

    void setRoot(Node* nroot) {
        root = nroot;
    }

    static Node* mergeWith(Node* a, Node* b) {
        if (a == nullptr)
            return b;
        if (b == nullptr)
            return a;
        if (a->key > b->key) {
            b->right = a->left;
            if (a->left != nullptr) a->left->parent = b;  // Actualizează părintele
            a->left = b;
            b->parent = a;  // Setează părintele
            a->rank++;
            return a;
        }
        else {
            a->right = b->left;
            if (b->left != nullptr) b->left->parent = a;  // Actualizează părintele
            b->left = a;
            a->parent = b;  // Setează părintele
            b->rank++;
            return b;
        }
    }

    void merge(Node* b) {
        if (root == nullptr) {
            root = b;
            return;
        }
        if (b == nullptr)
            return;
        if (root->key > b->key) {
            b->right = root->left;
            if (root->left != nullptr) root->left->parent = b;  // Actualizează părintele
            root->left = b;
            b->parent = root;  // Setează părintele
            root->rank++;
        }
        else {
            root->right = b->left;
            if (b->left != nullptr) b->left->parent = root;  // Actualizează părintele
            b->left = root;
            root->parent = b;  // Setează părintele
            b->rank++;
            root = b;
        }
    }

    int extractMin() {
        if (!root) return -1;

        int minVal = root->key;
        queue<Node*> q;
        Node* aux = root->left;

        while (aux) {
            q.push(aux);
            aux = aux->right;
        }

        delete root;
        root = nullptr;

        while (!q.empty()) {
            Node* a1 = q.front();
            q.pop();
            if (!q.empty()) {
                Node* a2 = q.front();
                q.pop();
                q.push(mergeWith(a1, a2));
            }
            else {
                root = mergeWith(root, a1);
            }
        }

        return minVal;
    }

    void push(int val) {
        Node* aux = new Node;
        aux->key = val;
        aux->rank = 0;
        merge(aux);
    }

    void decreaseKey(Node* node, int newKey) {
        if (newKey >= node->key) return;

        node->key = newKey;

        if (node == root) return;

        // Detach node from its current position
        if (node->parent) {
            if (node->parent->left == node) {
                node->parent->left = node->right;
            }
            else {
                Node* sibling = node->parent->left;
                while (sibling->right != node) {
                    sibling = sibling->right;
                }
                sibling->right = node->right;
            }
            if (node->right) {
                node->right->parent = node->parent;
            }
            node->parent = nullptr;
            node->right = nullptr;
        }

        merge(node);
    }
};
int main() {
    ifstream f("mergeheap.in");
    ofstream g("mergeheap.out");
    int n, q, op;
    RankPairingHeap R[NMAX];
    unordered_map<int, Node*> nodes; // Harta pentru a păstra referințele către noduri

    f >> n >> q;
    while (q--) {
        f >> op;
        switch (op) {
        case 1: {
            int idx, val;
            f >> idx >> val;
            R[idx].push(val);
            break;
        }
        case 2: {
            int idx;
            f >> idx;
            g << R[idx].extractMin() << "\n";
            break;
        }
        case 3: {
            int idx1, idx2;
            f >> idx1 >> idx2;
            R[idx1].merge(R[idx2].getRoot());
            R[idx2].setRoot();
            break;
        }
        case 4: { // Noua operație pentru decreaseKey
            int idx, oldKey, newKey;
            f >> idx >> oldKey >> newKey;
            Node* node = nodes[oldKey]; // Obține referința nodului din hartă
            if (node) {
                R[idx].decreaseKey(node, newKey);
                nodes.erase(oldKey); // Elimină vechea cheie din hartă
                nodes[newKey] = node; // Actualizează harta cu noua cheie
            }
            break;
        }
        }
    }
    f.close();
    g.close();
    return 0;
}