#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 1000000007ll
#define nmax 300002
#define lim 351
using namespace std;
typedef long long ll;
ifstream in("mergeheap.in");
ofstream out("mergeheap.out");
//FILE *fin=fopen("infasuratoare.in","r");
//FILE *fout=fopen("infasuratoare.out","w");
int n,m,t,i,j,k,l,e,f;
struct q{int v;q*f;q*r;}a[nmax],*w,*s[101],*c[nmax];
void me(q* x,q*y){
if(x&&y)
    if(x->v>y->v)y->r=x->f,x->f=y,w=x;
        else x->r=y->f,y->f=x,w=y;
    else w=x?x:y;
}
int main()
{
in>>n>>m;
while(m--){
    in>>t>>e;
    if(t==1)in>>a[++l].v,me(a+l,s[e]),s[e]=w;
    else if(t==3)in>>f,me(s[e],s[f]),s[e]=w,s[f]=0;
    else{
        out<<s[e]->v<<'\n';
        c[0]=s[e]->f,k=0;
        //cout<<8;
        while(c[k]&&c[k]->r)c[k+1]=c[k]->r->r,me(c[k],c[k]->r),c[k]=w,++k;
        if(!c[k])--k;
        while(k>0)me(c[k],c[k-1]),c[k-1]=w,k--;
        s[e]=c[0];
    }
}
}