Hack

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <stack>
#include <tuple>
#include <bitset>
#define ll long long
#define ull unsigned long long
#define ld long double
#define fp(a,b,c) for(int a=b;a<=c;a++)
#define fd(a,b,c) for(int a=b;a>=c;a--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f
#define base 127
#define mod 1000000007
#define eb emplace_back
#define pb pop_back
#define y1 y114
#define y0 y514
#define x1 x114
#define x0 x514
#define fill(x,y) memset(x,y,sizeof(x))
#define mpr make_pair
#define met(x,t) memset(x,t,sizeof(x))
#define fir first
#define sec second
#include <numeric>
#define int ll

using namespace std;

inline int rd(){
	int x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
	return x * f;}
const int N=1e5+10;
int n,q;
struct node{
	int v,son,nex;
	bool operator >(const node &x)const{return v>x.v;}
	bool operator == (const node &x)const{return v==x.v;}
}pa[N];
int f[N],vis[N];
int acc(int now){
	if(f[now]^now) return f[now]=acc(f[now]);
	return now;
}

int meld(int x,int y){
	if(!x||!y) return x|y;
	if(pa[x]>pa[y]||(pa[x]==pa[y]&&x>y)) swap(x,y);
	pa[y].nex=pa[x].son,pa[x].son=y,f[y]=x;
	return x;
}

int merge(int x){//合并x的兄弟们
	if(!pa[x].nex) return x;
	int y=pa[x].nex,z=pa[y].nex;
	pa[x].nex=pa[y].nex=0;
	return meld(meld(x,y),merge(z));
}
void del(int x){
	vis[x]=1;
	if(!pa[x].son) return ;
	int y=merge(pa[x].son);
	f[x]=f[y]=y;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 

	n=rd(),q=rd();
	iota(f+1,f+n+1,1);
	fp(i,1,n)
		pa[i].v=rd();
	while(q--){
		int op=rd(),x=rd(),y,z;
		if(op==1){
			y=rd();
			if((x^y)&&!vis[x]&&!vis[y]){
				x=acc(x),y=acc(y);
				z=meld(x,y);
				f[z]=z;
			}
		}else {
			if(vis[x]) cout << "-1" << endl;
			else {
				cout << pa[acc(x)].v << endl;
				del(acc(x));
			}
		}
	}
	return 0;
}

5 5
1 2 3 4 5
1 1 2
1 1 2
1 2 3
2 1
2 2