#include<bits/stdc++.h>
using namespace std;
template<class T,bool(*cmp)(register const T,register const T)>
class Heap
{
	private:	
		struct node{
			T x;
			int dist;
			node *l,*r,*fa;
			node()
			{
				l=NULL;
				r=NULL;
				fa=NULL;
				dist=1;
			}
		}*root,*swa;
		int len;
		inline int dis(node* x){return x==NULL?0:x->dist;}
		inline node* Merge(node* x,node* y)
		{
			if(x==NULL&&y==NULL)return NULL;
			else if(x==NULL)return y;
			else if(y==NULL)return x;
			if(!cmp(x->x,y->x))
			{
				swa=x;
				x=y;
				y=swa;
			}
			x->r=Merge(x->r,y);
			if(x->l==NULL)x->l=x->r,x->r=NULL;
			if(dis(x->r)>dis(x->l))
			{
				swa=x->l;
				x->l=x->r;
				x->r=swa;
			}
			x->dist=dis(x->r)+1;
			return x;
		}
	public:
		Heap(){root=NULL,root=0;}
		inline void push(register T x)
		{
			len=-~len;
			node* nx=new node;
			nx->x=x;
			root=Merge(root,nx);
		}
		inline void push(Heap a)
		{
			len+=a.len;
			root=Merge(root,a.root);
		}
		inline T top(){return root->x;}
		inline void pop(){root=Merge(root->l,root->r);}
		inline bool empty(){return len==0;}
		inline void clear()
		{
			root=NULL;
			len=0;
		}
};
unordered_map<int,int>fx;
int n,m,x,y,z,nx,ny,tx,f[200005],b[200005];
bool cmp(int x,int y){return x<y;}
Heap<int,cmp>q[200005];
int find(int x)
{
	if(f[x]!=x)
		f[x]=find(f[x]);
	return f[x];
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		fx[x]=i;
		f[i]=i;
		q[i].push(x);
	}
	while(m--)
	{
		cin>>x;
		if(x==1)
		{
			cin>>y>>z;
			nx=find(y),ny=find(z);
			if(b[y]||b[z])
				continue;
			q[nx].push(q[ny]);
			f[ny]=nx;
		}
		else if(x==2)
		{
			cin>>y;
			nx=find(y);
			if(b[y]||q[nx].empty())
				cout<<-1<<"\n";
			else
			{
				tx=q[nx].top();
				cout<<tx<<"\n";
				q[nx].pop();
				b[fx[tx]]=1;
			}
		}
	}
	return 0;
}