#include<stdio.h>
typedef struct O {
    int v;
    struct O *t,*i,*r;
}N;
N *W(int v)
{
    N *t=new N;
    t->i=t->r=NULL;
    t->v=v,t->r=t->i=NULL;
    return t;
}
N *M(N *a,N *b)
{
    if(!a)
        return b;
    if(!b)
        return a;
    N *z;
    if(b->v>a->v)
        z=a,a=b,b=z;
    if(!a->i) {
        a->i=b;
        return a;
    } else {
        b->r=a->i,a->i=b;
        return a;
    }
    return NULL;
}
N *I(int v,N *h)
{
    N *t=W(v);
    h=M(t,h);
    return h;
}
N *S(N *h)
{
    if(!h||!h->r)
        return h;
    else {
        N *c,*d,*e;
        c=h,d=h->r,e=h->r->r,c->r=d->r=NULL;
        return M(M(c,d),S(e));
    }
    return NULL;
}
N *D(N *h)
{
    printf("%d\n",h->v);
    return S(h->i);
}
int n,m,o,a,b;
N *u[105];
int main()
{
    freopen("mergeheap.in","r",stdin),freopen("mergeheap.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--) {
        scanf("%d",&o);
        if(o==1)
            scanf("%d%d",&a,&b),u[a]=I(b,u[a]);
        else if(o==2)
            scanf("%d",&a),u[a]=D(u[a]);
        else
            scanf("%d%d",&a,&b),u[a]=M(u[a],u[b]),u[b]=NULL;
    }
}