#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream fileIn("mergeheap.in");
ofstream fileOut("mergeheap.out");

class FHeap;
class Node {
private:
    Node* before;
    Node* after;
    Node* child;
    Node* parent;
    int value;
    int degree;
public:
    int getValue(){return value;}
    //Node(int val=0,Node* before = nullptr,Node* after = nullptr,Node*child = nullptr, Node* parent = nullptr);
    static Node* merge(Node* node,Node* otherNode);
    friend class FHeap;
    static void addChild(Node* p, Node* c);
};



Node* Node::merge(Node* node,Node* otherNode) {
    if(node == nullptr) return otherNode;
    if(otherNode == nullptr)  return node;
    if(node->getValue() <  otherNode->getValue()) { //interschimba
        Node* temporary = node;
        node = otherNode;
        otherNode = temporary;
    }
    Node* afterNode = node->after;
    Node* beforeONode = otherNode->before;
    node->after = otherNode;
    otherNode->before = node;
    afterNode-> before = beforeONode;
    beforeONode-> after = afterNode;

    return node;
}

void Node::addChild(Node* parent, Node* child) {
        child ->before = child->after = child;
        child->parent = parent;
        parent->degree++;
        parent->child = Node::merge(parent->child, child);
}



class FHeap {


public:
    Node* maxHeap;
    FHeap();
    void insert(int x); // pur si simplu pun in lista inlantuita
    void unionH(FHeap& otherH);
    int getMax(){return maxHeap->getValue();};
    void removeMax();
    Node* removeFromList(Node* node);
    Node* cleanup();
    void unparent(Node* node);



};
    FHeap::FHeap() {
        this->maxHeap = nullptr;
    }

Node* FHeap::cleanup() {
    Node* node = maxHeap;
    Node* degrees[70] ={nullptr};
    while(true) {
        if(degrees[node->degree]!= nullptr) { // am gasit un alt arbore de acelasi grad
            Node* t = degrees [node->degree]; // nodul de acelasi grad cu care tb sa il unesc
            if(t==node) { // e unul singur
                break;
            }
            degrees[node->degree] = nullptr; //
            if(node->value > t->value) {
                t->before->after = t->after;
                t->after-> before = t->before;
                Node::addChild(node,t);
            } else  {
                t->before->after = t->after;
                t->after->before = t->before;
                if(node->after == node) {
                    t-> after = t->before = t;
                    Node::addChild(t,node);
                    node=t;
                } else {
                    node->before -> after = t;
                    node->after->before= t;
                    t->before= node->before;
                    t->after = node->after;
                    Node::addChild(t, node);
                    node=t;
                }

            }
            continue;
        }else {
        degrees[node->degree] = node;
        }
        node=node->after;

    }
    Node* maxH = node;
    Node* start = node;
    do {
        if(node->value > maxH->value) {
            maxH = node;
        }
        node= node->after;
    }
    while (node != start );
    return maxH;
}

void FHeap::unparent(Node* node) {

    if(node== nullptr) {
        return;
    }
    Node* copyN = node;
    do {
        copyN->parent = nullptr;
        copyN = copyN->after;
    } while (copyN != node); // pana ajung circular la nod

}

Node* FHeap::removeFromList(Node* node) {
    if(node->after == node){ //daca e singurel
        node = node->child;
        return node;;
    }
    node->after->before = node->before;
    node->before->after = node->after;
    node = Node::merge(node->after, node->child);
    return node;
}


void FHeap::removeMax() {
    unparent(maxHeap->child);

    if(this->maxHeap == nullptr) {
        return;
    }
    maxHeap= removeFromList(maxHeap);
    if(maxHeap != nullptr) {
        maxHeap= cleanup();
    }
}




void FHeap::insert(int x) {
    Node* p = new Node;
    p-> value = x;
    p-> before = p->after = p;
    p->degree = 0;
    p ->parent = p->child = nullptr;
    maxHeap = Node::merge(maxHeap,p);


}

void FHeap::unionH(FHeap& otherH) {
    this->maxHeap = Node::merge(maxHeap, otherH.maxHeap);
    otherH.maxHeap= nullptr;

}





FHeap* heaps[101] = {nullptr};
int main()
{   int n, q, op, m, x, a,b; // nr multimi , nr op, op
    fileIn >> n >> q;

    for(int i = 0; i < q ; i++) {
        fileIn >> op;
        //fileOut <<op;
        switch (op) {
        case 1:
            fileIn >> m >> x;
            if(heaps[m] == nullptr) {
                //creez acum
                heaps[m] = new FHeap();
                heaps[m] ->insert(x);
            }
            else {
                heaps[m]->insert(x);
            }
            break;
        case 2:
            //afisez min +extrag
            fileIn >> m;
            //fileOut << heaps[m] ->getMax();
            fileOut << heaps[m]->getMax() <<'\n';
            heaps[m] ->removeMax();
            break;

        case 3:
            fileIn >>a>> b; // sa reunesc heaps[a], heaps[b];
            heaps[a]->unionH(*heaps[b]);
            break;
            }
    }


    return 0;
}