#include <bits/stdc++.h>
typedef long long ll;
#define fl(i) fhql[i]
#define fr(i) fhqr[i]
#define fdt(i) fhqdat[i]
#define frn(i) fhqran[i]
#define fsz(i) fhqsiz[i]
#define rd() read<ll>()
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
	T x = 0; bool f = false; char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = true;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}
template <typename T>
inline void write(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x / 10) write(x / 10);
	putchar((x % 10) ^ 48);
	return;
}
const int N = 5e4 + 5, M = 1e7 + 5;
const int INF = 0x7fffffff;
int n, m, a[N];
int cnt;
int fhql[M], fhqr[M];
int fhqdat[M], fhqran[M], fhqsiz[M];
struct Node {
	int root;
	int newnode(int x) {
		fdt(++ cnt) = x;
		frn(cnt) = rand();
		fsz(cnt) = 1;
		return cnt;
	}
	void update(int x) {
		fsz(x) = fsz(fl(x)) + fsz(fr(x)) + 1;
	}
	void split(int cur, int k, int &x, int &y) {
		if (!cur) x = y = 0;
		else {
			if (fdt(cur) <= k) {
				x = cur;
				split(fr(cur), k, fr(cur), y);
			}
			else {
				y = cur;
				split(fl(cur), k, x, fl(cur));
			}
			update(cur);
		}
	}
	int merge(int x, int y) {
		if (!x || !y) return x + y;
		if (frn(x) < frn(y)) {
			fr(x) = merge(fr(x), y);
			update(x); return x;
		}
		else {
			fl(y) = merge(x, fl(y));
			update(y); return y;
		}
	}
	int x, y, z;
	void ins(int k) {
		split(root, k, x, y);
		root = merge(merge(x, newnode(k)), y);
	}
	void del(int k) {
		split(root, k, x, z);
		split(x, k - 1, x, y);
		y = merge(fl(y), fr(y));
		root = merge(merge(x, y), z);
	}
	int get_dat(int x, int k) {
		if (k <= fsz(fl(x)))
			return get_dat(fl(x), k);
		if (k == fsz(fl(x)) + 1)
			return fdt(x);
		return get_dat(fr(x), k - fsz(fl(x)) - 1);
	}
	int get_rank(int k) {
		split(root, k - 1, x, y);
		int res = fsz(x) + 1;
		root = merge(x, y);
		return res;
	}
	int pre(int k) {
		split(root, k - 1, x, y);
		int res;
		if (fsz(x))
			res = get_dat(x, fsz(x));
		else res = -INF; 
		return res;
	}
	int nxt(int k) {
		split(root, k, x, y);
		int res;
		if (fsz(y))
			res = get_dat(y, 1);
		else res = INF;
		return res;
	}
	void build(int l, int r) {
		E(i, l, r)
			ins(a[i]); 
	} 
} fhqTreap[N << 2];
#define ls(x) x << 1
#define rs(x) x << 1 | 1
struct node {
	void build(int p, int l, int r) {
		fhqTreap[p].build(l, r);
		if (l != r) {
			int mid = l + r >> 1;
			build(ls(p), l, mid);
			build(rs(p), mid + 1, r);
		}
	}
	int get_rank(int p, int l, int r, int x, int y, int k) {
		if (r < x || l > y) return 0;
		if (x <= l && r <= y) return fhqTreap[p].get_rank(k) - 1;
		int mid = l + r >> 1; 
		return get_rank(ls(p), l, mid, x, y, k) + get_rank(rs(p), mid + 1, r, x, y, k);
	}
	int get_data(int l, int r, int k) {
		int x = 0, y = 1e8;
		int res = -1;
		while (x <= y) {
			int mid = x + y >> 1;
			if (get_rank(1, 1, n, l, r, mid) + 1 <= k) {
				res = mid;
				x = mid + 1;
			}
			else y = mid - 1;
		}
		return res;
	}
	void update(int p, int l, int r, int x, int k) {
		fhqTreap[p].del(a[x]);
		fhqTreap[p].ins(k);
		if (l != r) {
			int mid = l + r >> 1;
			if (x <= mid)
				update(ls(p), l, mid, x, k);
			else
				update(rs(p), mid + 1, r, x, k); 
		}
	}
	int pre(int p, int l, int r, int x, int y, int k) {
		if (r < x || l > y) return -INF;
		if (x <= l && r <= y) return fhqTreap[p].pre(k);
		int mid = l + r >> 1;
		return std::max(pre(ls(p), l, mid, x, y, k), pre(rs(p), mid + 1, r, x, y, k));
	}
	int nxt(int p, int l, int r, int x, int y, int k) {
		if (r < x || l > y) return INF;
		if (x <= l && r <= y) {
//			std::cout << p << ' ' << l << ' ' << r << ' ' << fhqTreap[p].nxt(k) << 'a' << '\n';
			return fhqTreap[p].nxt(k);
		}
		int mid = l + r >> 1;
		return std::min(nxt(ls(p), l, mid, x, y, k), nxt(rs(p), mid + 1, r, x, y, k));
	}
} ST;
int main() {
	srand(1027); rand();
	n = rd(); m = rd();
	E(i, 1, n)
		a[i] = rd();
	ST.build(1, 1, n);
	while (m --) {
		int opt; opt = rd();
		if (opt == 1) {
			int l, r, k;
			l = rd(); r = rd(); k = rd();
			write(ST.get_rank(1, 1, n, l, r, k) + 1);
			puts("");
		}
		else if (opt == 2) {
			int l, r, k;
			l = rd(); r = rd(); k = rd();
			write(ST.get_data(l, r, k));
			puts("");
		}
		else if (opt == 3) {
			int x, k;
			x = rd(); k = rd();
			ST.update(1, 1, n, x, k);
		}
		else if (opt == 4) {
			int l, r, k;
			l = rd(); r = rd(); k = rd();
			write(ST.pre(1, 1, n, l, r, k));
			puts("");
		}
		else {
			int l, r, k;
			l = rd(); r = rd(); k = rd();
			write(ST.nxt(1, 1, n, l, r, k));
			puts("");
		}
	}
	return 0;
}