#include <bits/stdc++.h>
using namespace std;
const int N = 50005, INF = 2147483647;
int n, m, a[N], b[N * 2], u, op[N], x[N], y[N], k[N], tot, rt[N], t1, t2, v1[25], v2[25];
struct node { int l, r, v; } c[N << 8];
void upd(int &p, int l, int r, int x, int d) {
	if (!p) p = ++tot;
	if (l == r) return void(c[p].v += d);
	int mid = l + r >> 1;
	if (x <= mid) upd(c[p].l, l, mid, x, d);
	else upd(c[p].r, mid + 1, r, x, d);
	c[p].v = c[c[p].l].v + c[c[p].r].v;
}
void add(int x, int d) {
	for (int i = x; i <= n; i += i & -i) upd(rt[i], 1, u, a[x], d);
}
void init(int l, int r) {
	t1 = t2 = 0, l--;
	while (r) v1[++t1] = rt[r], r -= r & -r;
	while (l) v2[++t2] = rt[l], l -= l & -l;
}
int getkth(int l, int r, int k) {
	if (l == r) return l;
	int mid = l + r >> 1, x = 0;
	for (int i = 1; i <= t1; i++) x += c[c[v1[i]].l].v;
	for (int i = 1; i <= t2; i++) x -= c[c[v2[i]].l].v;
	if (k <= x) {
		for (int i = 1; i <= t1; i++) v1[i] = c[v1[i]].l;
		for (int i = 1; i <= t2; i++) v2[i] = c[v2[i]].l;
		return getkth(l, mid, k);
	} else {
		for (int i = 1; i <= t1; i++) v1[i] = c[v1[i]].r;
		for (int i = 1; i <= t2; i++) v2[i] = c[v2[i]].r;
		return getkth(mid + 1, r, k - x);
	}
}
int kth(int l, int r, int k) { return init(l, r), getkth(1, u, k); }
int getrnk(int l, int r, int k) {
	if (l == r) return 0;
	int mid = l + r >> 1, x = 0;
	if (k <= mid) {
		for (int i = 1; i <= t1; i++) v1[i] = c[v1[i]].l;
		for (int i = 1; i <= t2; i++) v2[i] = c[v2[i]].l;
		return getrnk(l, mid, k);
	} else {
		for (int i = 1; i <= t1; i++) x += c[c[v1[i]].l].v;
		for (int i = 1; i <= t2; i++) x -= c[c[v2[i]].l].v;
		for (int i = 1; i <= t1; i++) v1[i] = c[v1[i]].r;
		for (int i = 1; i <= t2; i++) v2[i] = c[v2[i]].r;
		return x + getrnk(mid + 1, r, k);
	}
}
int rnk(int l, int r, int k) { return init(l, r), getrnk(1, u, k) + 1; }
int pre(int l, int r, int k) {
	int x = rnk(l, r, k) - 1;
	return x ? kth(l, r, x) : 0;
}
int nxt(int l, int r, int k) {
	if (k == u) return u + 1;
	int x = rnk(l, r, k + 1);
	if (x == r - l + 2) return u + 1;
	return kth(l, r, x);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[++u] = i;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &op[i], &x[i], &y[i]);
		if (op[i] == 3) b[++u] = y[i];
		else {
			scanf("%d", &k[i]);
			if (op[i] != 2) b[++u] = k[i];
		}
	}
	sort(b + 1, b + 1 + u);
	u = unique(b + 1, b + 1 + u) - b - 1;
	b[0] = -INF, b[u + 1] = INF;
	#define to(x) (lower_bound(b + 1, b + 1 + u, x) - b)
	for (int i = 1; i <= n; i++) a[i] = to(a[i]), add(i, 1);
	for (int i = 1; i <= m; i++) {
		if (op[i] == 3) y[i] = to(y[i]);
		else if (op[i] != 2) k[i] = to(k[i]);
	}
	for (int i = 1; i <= m; i++) {
		if (op[i] == 1) printf("%d\n", rnk(x[i], y[i], k[i]));
		else if (op[i] == 2) printf("%d\n", b[kth(x[i], y[i], k[i])]);
		else if (op[i] == 3) add(x[i], -1), a[x[i]] = y[i], add(x[i], 1);
		else if (op[i] == 4) printf("%d\n", b[pre(x[i], y[i], k[i])]);
		else printf("%d\n", b[nxt(x[i], y[i], k[i])]);
	}
}