#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int MAXN=1e5+2,mod=998244353,inf=0x3f3f3f3f;
typedef long long ll;
int n,m,a[MAXN];
struct LSH{
	int x,id;
	bool operator<(const LSH& o) const{
		if(x==o.x)
			return id<o.id;
		return x<o.x;
	}
}lsh[MAXN];
struct EDGE{
	int to,next;
}e[MAXN<<1];
int cnt=0,head[MAXN];
inline void addedge(int u,int v){
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
#define toi e[i].to
#define fore(now,i) for(int i=head[now];~i;i=e[i].next)
int ans[MAXN];
short op[MAXN];
struct Query{
	int x,y;
}q[MAXN];
const int block_size=2500;
int f[MAXN],dp[MAXN];
int sz[MAXN][MAXN/block_size+2],len;
struct Ctrl_Z{
	int x,y;
	bool is_plus;
};
class Stack{
	Ctrl_Z _m[MAXN];
	int tp;
public:
	Stack():tp(0){}
	inline void push(const Ctrl_Z& o){
		_m[++tp]=o;
	}
	inline void pop(){
		--tp;
	}
	inline Ctrl_Z& top(){
		return _m[tp];
	}
	inline bool empty(){
		return !tp;
	}
}ctrl_z;
int findf(int x){
	return f[x]==x?x:findf(f[x]);
}
inline bool merge(int x,int y){
	x=findf(x),y=findf(y);
	if(x==y)
		return false;
	if(dp[x]>dp[y])
		swap(x,y);
	f[x]=y;
	if(dp[x]==dp[y]){
		++dp[y];
		ctrl_z.push({x,y,1});
		for(int i=1;i<=len;i++)
			sz[y][i]+=sz[x][i];
	}else
		ctrl_z.push({x,y,0});
	return true;
}
inline void getback(){
	if(ctrl_z.empty())
		return ;
	Ctrl_Z& l=ctrl_z.top();
	if(l.is_plus)
		--dp[l.y];
	f[l.x]=l.x;
	for(int i=1;i<=len;i++)
		sz[l.y][i]-=sz[l.x][i];
	ctrl_z.pop();
}
int id[MAXN];
void dfs(int now){
	bool ismerge=false;
	int x=q[now].x,y=q[now].y;
	if(op[now]==1)
		ismerge=merge(x,y);
	else if(op[now]==3){
		x=findf(x);
		ans[now]=-1;
		for(int i=1;i<=len;y-=sz[x][i++])
			if(y<=sz[x][i]){
				for(int j=(i-1)*block_size+1;j<=min(n,i*block_size);j++)
					if(findf(id[j])==x)
						if(!--y){
							ans[now]=lsh[j].x;
							break;
						}
				break;
			}
	}
	fore(now,i)
		dfs(toi);
	if(ismerge)
		getback();
}
#define belong(x) (((x)+block_size-1)/block_size)
signed main(){
//	freopen("std.in","r",stdin);
//	freopen("ans.out","w",stdout);
	memset(head,-1,sizeof(head));
	memset(e,-1,sizeof(e));
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m;
	len=belong(n);
	for(int i=1;i<=n;i++){
		cin>>lsh[i].x;
		lsh[i].id=i;
	}
	sort(lsh+1,lsh+n+1);
	for(int i=1;i<=n;i++)
		a[lsh[i].id]=i;
	for(int i=1;i<=n;i++){
		sz[f[i]=i][belong(a[i])]=1;
		id[a[i]]=i;
		dp[i]=1;
	}
	for(int i=1,x,y;i<=m;i++){
		cin>>op[i]>>x;
		if(op[i]==2)
			addedge(x,i);
		else{
			cin>>y;
			addedge(i-1,i);
		}
		q[i]={x,y};
	}
	dfs(0);
	for(int i=1;i<=m;i++)
		if(op[i]==3)
			cout<<ans[i]<<'\n';
	return 0;
}
/*

6 10
816801151 223885531 110182151 94271893 319888699 106363731 
1 1 3
1 3 5
1 2 4
1 4 6
1 1 2
3 1 1
2 4
1 1 2
3 1 4
2 7

*/

拍过了，但是找不出错。