#include<bits/stdc++.h>
#define int long long
#define lc p << 1
#define rc p << 1 | 1
using namespace std;
const int maxn = 5e4 + 10;
struct tree {
	int l, r, root, tot;
	struct node {
		int s[2], val, key, size;
	};
	vector<node> tr; 
	inline int build(int x) {
		if (!tr.size()) tr.push_back({{0, 0}, 0, 0, 0});
		tr.push_back({{0, 0}, x, rand(), 1});
		return tr.size() - 1;
	}
	inline void pushup(int p) {
		if (p == 0) tr[p].size = 0;
		else tr[p].size = tr[tr[p].s[0]].size + tr[tr[p].s[1]].size + 1;
	}
	inline void split(int p, int val, int &x, int &y) {
		if (!p) {
			x = y = 0;
			return;
		}
		if (tr[p].val <= val) {
			x = p;
			split(tr[p].s[1], val, tr[p].s[1], y);
			pushup(p);
			return;
		}
		else {
			y = p;
			split(tr[p].s[0], val, x, tr[p].s[0]);
			pushup(p);
			return;
		}
	}
	inline int merge(int x, int y) {
		if (!x || !y) return x + y;
		if (tr[x].key <= tr[y].key) {
			tr[x].s[1] = merge(tr[x].s[1], y);
			pushup(x);
			return x;
		}
		else {
			tr[y].s[0] = merge(x, tr[y].s[0]);
			pushup(y);
			return y;
		}
	}
	inline void insert(int x) {
		int xx, yy, zz;
		split(root, x, xx, yy);
		zz = build(x);
		root = merge(merge(xx, zz), yy);
		pushup(root);
	}
	inline void delet(int x) {
		int xx, yy, zz;
		split(root, x, xx, yy);
		split(xx, x - 1, xx, zz);
		tr[zz].size = 0;
		zz = merge(tr[zz].s[0], tr[zz].s[1]);
		root = merge(merge(xx, zz), yy);
		pushup(root);
	}
	inline int get(int x) {
		int xx, yy, ans;
		split(root, x - 1, xx, yy);
		ans = tr[xx].size;
		root = merge(xx, yy);
		return ans;
	}
	inline int pre(int x) {
		int xx, yy;
		split(root, x - 1, xx, yy);
		if (!tr[xx].size) return -2147483647;
		for (; tr[xx].s[1]; xx = tr[xx].s[1]);
		root = merge(xx, yy);
		return tr[xx].val;
	}
	inline int net(int x) {
		int xx, yy;
		split(root, x, xx, yy);
		if (!tr[yy].size) return 2147483647;
		for (; tr[yy].s[0]; yy = tr[yy].s[0]);
		root = merge(xx, yy);
		return tr[yy].val;
	}
} t[maxn << 2];
int n, m, op, l, r, x, pos, a[maxn];
void build(int p, int l, int r) {
	t[p].l = l; t[p].r = r;
	for (int i = l; i <= r; i++) t[p].insert(a[i]);
	if (l == r) return;
	int mid = l + r >> 1;
	build(lc, l, mid); build(rc, mid + 1, r);
}
int getrank(int p, int l, int r, int x) {
	if (t[p].l >= l && t[p].r <= r) return t[p].get(x);
	int mid = t[p].l + t[p].r >> 1, ans = 0;
	if (l <= mid) ans += getrank(lc, l, r, x);
	if (r > mid) ans += getrank(rc, l, r, x);
	return ans;
}
void change(int p, int x, int y) {
	t[p].delet(a[x]);
	t[p].insert(y);
	if (t[p].l == t[p].r) return;
	int mid = t[p].l + t[p].r >> 1;
	if (x <= mid) change(lc, x, y);
	else change(rc, x, y);
}
int getpre(int p, int l, int r, int x) {
	if (t[p].l >= l && t[p].r <= r) return t[p].pre(x);
	int mid = t[p].l + t[p].r >> 1, res = -2147483647;
	if (l <= mid) res = max(res, getpre(lc, l, r, x));
	if (r > mid) res = max(res, getpre(rc, l, r, x));
	return res;
}
int getnet(int p, int l, int r, int x) {
	if (t[p].l >= l && t[p].r <= r) return t[p].net(x);
	int mid = t[p].l + t[p].r >> 1, res = 2147483647;
	if (l <= mid) res = min(res, getnet(lc, l, r, x));
	if (r > mid) res = min(res, getnet(rc, l, r, x));
	return res;
}
signed main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", a + i);
	build(1, 1, n);
	while (m--) {
		scanf("%lld", &op);
		if (op == 1) {
			scanf("%lld%lld%lld", &l, &r, &x);
			printf("%lld\n", getrank(1, l, r, x) + 1);
		}
		if (op == 2) {
			scanf("%lld%lld%lld", &l, &r, &x);
			int ll = l, rr = r;
			while (ll < rr) {
				int mid = ll + rr + 1 >> 1;
				if (getrank(1, l, r, mid) + 1 <= x) ll = mid;
				else rr = mid - 1;
			}
			printf("%lld\n", ll);
		}
		if (op == 3) {
			scanf("%lld%lld", &pos, &x);
			change(1, pos, x);
			a[pos] = x;
		}
		if (op == 4) {
			scanf("%lld%lld%lld", &l, &r, &x);
			printf("%lld\n", getpre(1, l, r, x));
		}
		if (op == 5) {
			scanf("%lld%lld%lld", &l, &r, &x);
			printf("%lld\n", getnet(1, l, r, x));
		}
	}
	return 0;
}
/*
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

9 6
4 2 2 10 9 4 0 1 1

2
4
3
4
9
*/