#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

struct nod
{
    nod *st;
    nod *dr;
    nod *parinte;
    nod *partener;
    nod *copil;

    long long cheie;
    long long dim;
    bool de_ech;
};

struct heap
{
    nod **arbori;
    int max_arbori;
    int nr_noduri;
    long long val;
};

void initializareHeap(heap *H, int max_noduri)
{
    H->max_arbori = (int) (log(max_noduri + 1) / log(2.0));
    H->arbori = new nod *[H->max_arbori];
    H->nr_noduri = H->val = 0;

    for (int i = 0; i < H->max_arbori; i++)
    {
        H->arbori[i] = NULL;
    }
}

nod *creareNod(long long cheie)
{
    nod *n = new nod();
    n->cheie = cheie;
    n->dim = 0;
    n->de_ech = false;
    n->copil = n->parinte = n->partener = n->st = n->dr = NULL;

    return n;
}

void adaugareNodCopil(nod *h, nod *n)
{
    nod *st, *dr;

    st = h->copil;
    if (st != NULL)
    {
        dr = st->dr;
        n->st = st;
        n->dr = dr;
        dr->st = n;
        st->dr = n;
    }
    else
    {
        n->st = n->dr = n;
    }

    h->copil = n;
    n->parinte = h;
}

int mergeNoduri(nod **a, nod **b)
{
    nod *arbore, *urm, *alt, *urm_alt;

    int c = 0;

    //merge alt in arbore, in functie de cheie
    if ((*a)->cheie >= (*b)->cheie) {
        arbore = (*a);
        alt = (*b);
    } else {
        arbore = (*b);
        alt = (*a);
    }
    c++;

    urm = arbore->partener;
    urm_alt = alt->partener;

    if (urm == NULL)
    {
        if (urm_alt != NULL)
        {
            adaugareNodCopil(arbore, alt);
            (arbore->dim)++;

            (*a) = NULL;
            (*b) = arbore;
        }
        else
        {
            arbore->partener = alt;
            alt->partener = arbore;
            alt->de_ech = true;

            (*a) = arbore;
            (*b) = NULL;
        }
    }
    else if (urm_alt == NULL)
    {
        arbore->partener = NULL;
        alt->partener = urm;
        urm->partener = alt;

        if (alt->cheie > urm->cheie)
        {
            adaugareNodCopil(arbore, alt);
        }
        else
        {
            urm->de_ech = false;
            alt->de_ech = true;
            adaugareNodCopil(arbore, urm);
        }

        (arbore->dim)++;

        c++;
        (*a) = NULL;
        (*b) = arbore;
    }
    else
    {
        arbore->partener = NULL;
        urm->partener = NULL;
        urm->de_ech = false;
        urm->st = urm->dr = urm;
        urm->parinte = NULL;

        adaugareNodCopil(arbore, alt);
        (arbore->dim)++;

        (*a) = urm;
        (*b) = arbore;
    }

    return c;
}

void aranjareHeap(heap *H, nod *lista)
{
    nod *urm, *de_aranjat, *de_mutat;
    long long d;

    de_aranjat = lista;
    de_mutat = NULL;

    do
    {
        if (de_aranjat != NULL)
        {
            urm = de_aranjat->dr;
            de_aranjat->dr = de_aranjat->st = de_aranjat;
            de_aranjat->parinte = NULL;
        }
        else
        {
            de_aranjat = de_mutat;
            de_mutat = NULL;
        }

        if (de_mutat != NULL)
        {
            mergeNoduri(&de_aranjat, &de_mutat);
        }

        if (de_aranjat != NULL)
        {
            d = de_aranjat->dim;
            if (H->arbori[d] != NULL) {
                mergeNoduri(&(H->arbori[d]), &de_aranjat);
                if(H->arbori[d] == NULL)
                    H->val -= (1 << d);
                de_mutat = de_aranjat;
            }
            else
            {
                H->arbori[d] = de_aranjat;
                H->val += (1 << d);
            }
        }

        de_aranjat = urm;
    }
    while (de_aranjat != NULL || de_mutat != NULL);
}

nod *inserare(heap *H, long long cheie)
{
    nod *n = creareNod(cheie);
    aranjareHeap(H, n);
    H->nr_noduri ++;

    return n;
}

nod *aflareNodMax(heap *H)
{
    nod *nod_max, *urm;
    long long k, k2;
    long long r, v;

    v = H->val;
    r = -1;
    while (v != 0) {
        v = v >> 1;
        r++;
    }

    nod_max = H->arbori[r];
    k = nod_max->cheie;

    while (r > 0) {
        r--;
        urm = H->arbori[r];
        if (urm) {
            if ((k2 = urm->cheie) > k) {
                k = k2;
                nod_max = urm;
            }
        }
    }

    return nod_max;
}

void stergereMax(heap *H, nod *nod_max)
{
    nod *copil, *urm, *partener;

    long long r = nod_max->dim;
    if ((partener = nod_max->partener))
    {
        partener->partener = NULL;
        partener->parinte = NULL;
        partener->st = partener->dr = partener;
        H->arbori[r] = partener;
    }
    else
    {
        H->arbori[r] = NULL;
        H->val -= (1 << r);
    }
    H->nr_noduri --;

    copil = nod_max->copil;
    if (copil)
    {
        urm = copil->dr;
        urm->st = copil->dr = NULL;
        aranjareHeap(H, urm);
    }
}

bool mergeHeap(heap *H1, heap *H2)
{
    for (int i = 0; i < H2->max_arbori; i++)
    {
        if (H2->arbori[i] != NULL)
        {
            H2->arbori[i]->dr = H2->arbori[i]->st = NULL;
            aranjareHeap(H1, H2->arbori[i]);
            H2->arbori[i] = NULL;
        }
    }
    H1->nr_noduri += H2->nr_noduri;
    H2->nr_noduri = 0;

    return true;
}

int main()
{
    int n, q, op;

    in>>n>>q;

    heap *H[n+1];
    for(int i=1; i<=n; i++)
    {
        H[i] = new heap;
        initializareHeap(H[i], 500000);
    }

    int nr_heap, nr_heap2;
    long long cheie_nod;
    nod *nod_max;

    for(int i=0; i<q; i++)
    {
        in>>op;
        switch(op)
        {
            case 1: //inserare
                in>>nr_heap>>cheie_nod;
                inserare(H[nr_heap], cheie_nod);
                break;
            case 2: //stergere maxim
                in>>nr_heap;
                nod_max = aflareNodMax(H[nr_heap]);
                out<<nod_max->cheie<<'\n';
                stergereMax(H[nr_heap], nod_max);
                break;
            case 3: //merge
                in>>nr_heap>>nr_heap2;
                mergeHeap(H[nr_heap], H[nr_heap2]);
                break;
        }
    }

    return 0;
}