#include<bits/stdc++.h>
#define endl '\n'
#define rd read()
using namespace std;
const int N = 1e5 + 5;
const int block = N / 46;
const int B = N / block + 5;
struct Query {
	int x, y, opt;
} q[N];
struct Edge {
	int v, next;
} e[N];
int st[B], ed[B];
int n, m, a[N], b[N], tot, ans[N], pos[N], tmp[N];
int cnt, head[N];
short f[N][B];
struct Dsu {
	int fa[N], siz[N];
	void init() {
		for (int i = 1; i <= n; i++) siz[fa[i] = i] = 1;
	}
	inline int find(int x) {
		while (x ^ fa[x]) x = fa[x];
		return fa[x];
	}
	inline void merge(int x, int y) {
		if (siz[x] < siz[y]) swap(x, y);
		fa[y] = x, siz[x] += siz[y];
		for (int i = 1; i <= tot; i++) f[x][i] += f[y][i];
	}
} d;
inline int read() {
	int x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x;
}
inline void add(int u, int v) {
	e[++cnt] = {v, head[u]};
	head[u] = cnt;
}
void init() {
	tot = (n - 1) / block + 1;
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
		a[i] += tmp[a[i]]++;
		pos[a[i]] = i;
		f[i][(a[i] - 1) / block + 1] = 1;
	}
	for (int i = 1; i <= tot; i++) st[i] = (i - 1) * block + 1, ed[i] = min(n, i * block);
}
void dfs(int u) {
	int fx = d.find(q[u].x), fy = d.find(q[u].y);
	if (q[u].opt == 1) {if (fx ^ fy) d.merge(fx, fy);}
	else if (q[u].opt == 3) {
		if (q[u].y > d.siz[fx]) ans[u] = -1;
		else {
			int y = q[u].y;
			for (int i = 1; i <= tot; i++) {
				if (y <= f[fx][i]) {
					for (int j = st[i]; j <= ed[i]; j++) {
						if (d.find(pos[j]) == fx) {
							y--;
							if (!y) {
								ans[u] = b[j];
								break ;
							}
						}
					}
					break ;
				}
				y -= f[fx][i];
			}
		}
	}
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		dfs(v);
	}
	if (q[u].opt == 1 && fx ^ fy) {
		d.siz[fx] -= d.siz[fy]; d.fa[fy] = fy;
		for (int i = 1; i <= tot; i++) f[fx][i] -= f[fy][i];
	}
}
signed main() {
	n = rd, m = rd;
	for (int i = 1; i <= n; i++) b[i] = a[i] = rd;
	d.init();
	init();
	for (int i = 1; i <= m; i++) {
		q[i].opt = rd;
		if (q[i].opt == 1) q[i].x = rd, q[i].y = rd, add(i - 1, i);
		else if (q[i].opt == 2) add(rd, i);
		else add(i - 1, i), q[i].x = rd, q[i].y = rd;
	}
	dfs(0);
	for (int i = 1; i <= m; i++) if (q[i].opt == 3) printf("%d\n", ans[i]);
	return 0;
}