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

ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

struct Node{
    int x;
    Node* fiu;
    Node* frate;

    Node(int x){
        this->x = x;
        this->fiu = NULL;
        this->frate = NULL;
    }
};

class Heap{
    Node* radacina;

public:
    Heap() {this->radacina = NULL;}

    void extrageMax();
    void insereaza(int x);
    void merge(Node*);
    Node* merge(Node*, Node*);
    void merge(Heap&);
    Node* metoda_2_pass(Node*);

};

void Heap::merge(Node* rad){
    if(this->radacina == NULL)
        this->radacina = rad;
    else
        if(rad != NULL){
            if(this->radacina->x < rad->x)
                swap(this->radacina, rad);
            rad->frate = this->radacina->fiu;
            this->radacina->fiu = rad;
            rad = NULL;
        }
}

Node* Heap::merge(Node* r1, Node* r2){
    if(r1 == NULL){
        r1 = r2;
        return r1;
    }
    if(r2 == NULL)
        return r1;

    if(r1->x < r2->x)
        swap(r1, r2);

    r2->frate = r1->fiu;
    r1->fiu = r2;
    return r1;
}

void Heap::merge(Heap& h){
    this->merge(h.radacina);
    h.radacina = NULL;
}

void Heap::insereaza(int x){
    if(this->radacina == NULL)
        this->radacina = new Node(x);
    else{
        Node* n = new Node(x);
        merge(n);
    }
}

Node* Heap::metoda_2_pass(Node* fiu){
    if(fiu == NULL || fiu->frate == NULL)
        return fiu;
    else{
        Node* nod = fiu;
        Node* frateNod = fiu->frate;
        Node* frateNod2 = fiu->frate->frate;

        nod->frate = NULL;
        frateNod->frate = NULL;
        return merge(merge(nod, frateNod), metoda_2_pass(frateNod2));
    }
}

void Heap::extrageMax(){
    if(this->radacina != NULL){
         g << this->radacina->x;
        Node* copie = this->radacina;
        if(this->radacina->fiu != NULL){
            this->radacina = metoda_2_pass(this->radacina->fiu);
        }
        delete copie;
    }
}

int main(){
    Heap h[101];

    int n, nrOp, op, poz, x, poz2;
    f >> n >> nrOp;

    for(int i = 0; i < nrOp; i++){
        f >> op;
        switch(op){
            case 1:{
                f >> poz >> x;
                h[poz].insereaza(x);
                break;
            }
            case 2:{
                f >> poz;
                h[poz].extrageMax();
                g << "\n";
                break;
            }
            case 3:{
                f >> poz >> poz2;
                h[poz].merge(h[poz2]);
                break;
            }
        }
    }
    f.close();
    g.close();
    return 0;
}