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

ifstream f("mergeheap.in");
ofstream g("mergeheap2.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);
    Node* merge(Node* rad1, Node* rad2);
    void merge(Heap*);
    Node* metoda_2_pass(Node*);
};

Node* Heap::merge(Node* rad1, Node* rad2){
    if(rad1 == NULL)
        return rad2;
    if(rad2 == NULL)
        return rad1;

    if(rad1->x < rad2->x){
        rad1->frate = rad2->fiu;
        rad2->fiu = rad1;
        return rad2;
    }
    else{
        rad2->frate = rad1->fiu;
        rad1->fiu = rad2;
        return rad1;
    }
}

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

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

Node* Heap::metoda_2_pass(Node* nod){
    if(nod == NULL || nod->frate == NULL)
        return nod;
    else{
        Node* fr = nod->frate;
        Node* fr2 = nod->frate->frate;
        nod->frate = NULL;
        fr->frate = NULL;
        return merge(merge(nod, fr), metoda_2_pass(fr2));
    }
}

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

int main(){
    Heap h[101];

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

    while(nrOp){
        nrOp--;
        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;
}