#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359
#define mod 1000000007
#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++)
using namespace std;
typedef long long ll;
ifstream in("mergeheap.in");
ofstream out("mergeheap.out");
int q,n,m,a[300001]={-1},f[300001],r[300001],c[300001],s[101],x,y,w,i,j,k,l;
#define m(g,h)r[g]=r[h]=0;\
        if(a[g]>a[h])\
            r[h]=f[g],f[g]=h,w=g;\
            else r[g]=f[h],f[h]=g,w=h;
int main()
{
in>>n>>q;
for(i=1;i<=q;i++)
{
    in>>n;
    if(n==1)
    {
        in>>x>>a[i];
        if(s[x]==0)
            s[x]=i;
            else{
                m(s[x],i);
                //cout<<a[f[s[x]]]<<'\n';
                if(w==i)s[x]=i;
                //cout<<a[f[s[x]]]<<'\n';
            }
    }
    else if(n==3)
    {
        in>>x>>y;
        if(s[y])
            if(s[x])
        {
            m(s[x],s[y]);
            s[x]=w,s[y]=0;
        }
            else s[x]=y,s[y]=0;
    }
    else{
        in>>x;
        out<<a[s[x]]<<'\n';
        if(f[s[x]]==0)
            s[x]=0;
            else{
            c[0]=f[s[x]],l=0;
            while(r[c[l]])c[l+1]=r[c[l]],++l;
            for(j=1;j<=l;j+=2)
            {
                m(c[j],c[j-1]);
                c[j-1]=w;
            }
            l=l/2*2-2;
            while(l>=0)
            {
                m(c[l],c[l+2]);
                c[l]=w;
                l-=2;
            }
            s[x]=c[0];
            //cout<<i<<' '<<a[s[x]]<<'\n';
        }

    }
}
}