#include<bits/stdc++.h>
using namespace std;
#define lid (id << 1)
#define rid (id << 1 | 1)
const int N = 5e4+5, M = 1e7+5;
int ls[M], rs[M], key[M], pri[M], siz[M], tsiz;
struct fhqtreap{
	int root = 0;
	void update(int rt){
		siz[rt] = siz[ls[rt]] + siz[rs[rt]] + 1;
	}
	void newnode(int x){
		++tsiz;
		siz[tsiz] = 1;
		ls[tsiz] = rs[tsiz] = 0;
		key[tsiz] = x;
		pri[tsiz] = rand();
	}
	void split(int rt, int x, int &l, int &r){
		if (rt == 0){
			l = r = 0;
			return;
		}
		if (key[rt] <= x) l = rt, split(rs[rt], x, rs[rt], r);
		else r = rt, split(ls[rt], x, l, ls[rt]);
		update(rt);
	}
	int merge(int l, int r){
		if (l == 0 || r == 0) return l + r;
		if (pri[l] > pri[r]){
			rs[l] = merge(rs[l], r);
			update(l);
			return l;
		}
		else{
			ls[r] = merge(l, ls[r]);
			update(r);
			return r;
		}
	}
	void insert(int x){
		int l, r;
		split(root, x, l, r);
		newnode(x);
		root = merge(merge(l, tsiz), r);
	}
	void del(int x){
		int l, m, r;
		split(root, x, l, r);
		split(l, x - 1, l, m);
		m = merge(ls[m], rs[m]);
		root = merge(merge(l, m), r);
	}
	int getrank(int x){
		int l, r, res;
		split(root, x - 1, l, r);
		res = siz[l] + 1;
		root = merge(l, r);
		return res - 1;
	}
	int kth(int rt, int k){
		if (k == siz[ls[rt]] + 1) return rt;
		if (k <= siz[ls[rt]]) return kth(ls[rt], k);
		return kth(rs[rt], k - siz[ls[rt]] - 1);
	}
	int getkth(int k){
		return key[kth(root, k)];
	}
	int pre(int x){
		int l, r, res;
		split(root, x - 1, l, r);
		res = key[kth(l, siz[l])];
		root = merge(l, r);
		return res;
	}	
	int suc(int x){
		int l, r, res;
		split(root, x, l, r);
		res = key[kth(r, 1)];
		root = merge(l, r);
		return res;
	}
}t[N << 2];
struct node{
	int l, r;
}tr[N << 2];
int root[N << 2], a[N], n, q;
void build (int id, int l, int r){
	tr[id].l = l;
	tr[id].r = r;
	for (int i = l;i <= r;i++) t[id].insert(a[i]);
	t[id].insert(2147483647);
	t[id].insert(-2147483647);
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(lid, l, mid);
	build(rid, mid + 1, r);
}
int qrank(int id, int l, int r, int x){
	if (tr[id].r < l || tr[id].l > r) return 0;
	if (l <= tr[id].l && tr[id].r <= r) return t[id].getrank(x) - 1;
	return qrank(lid, l, r, x) + qrank(rid, l, r, x);
}
int qkth(int l, int r, int rk){
	int x = 0, y = 1e8, res = -1;
	while (x <= y){
		int mid = (x + y) >> 1;
		int tmp = qrank(1, l, r, mid) + 1;
		if (tmp == rk) return mid;
		if (tmp < rk){
			res = mid;
			x = mid + 1;
		}
		else y = mid - 1;
		//cout << mid << ' ' << tmp << '\n';
	}
	return res;
}
void update(int id, int pos, int k){
	t[id].del(a[pos]);
	t[id].insert(k);
	if (tr[id].l == tr[id].r) return;
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (pos <= mid) update(lid, pos, k);
	else update(rid, pos, k);
}
int qpre(int id, int l, int r, int k){
	if (tr[id].r < l || tr[id].l > r) return -2147483647;
	if (l <= tr[id].l && tr[id].r <= r){
		return t[id].pre(k);
	}
	return max(qpre(lid, l, r, k), qpre(rid, l, r, k));
}
int qsuc(int id, int l, int r, int k){
	if (tr[id].r < l || tr[id].l > r) return 2147483647;
	if (l <= tr[id].l && tr[id].r <= r) return t[id].suc(k);
	return min(qsuc(lid, l, r, k), qsuc(rid, l, r, k));
}
int main(){
	srand(time(NULL));
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	build(1, 1, n);
	while (q--){
		int op, pos, l, r, k;
		cin >> op;
		if (op == 3){
			cin >> pos >> k;
			update(1, pos, k);
			a[pos] = k;
		}
		else{
			cin >> l >> r >> k;
			if (op == 1){
				cout << qrank(1, l, r, k) + 1 << '\n';
			}
			else if (op == 2){
				cout << qkth(l, r, k) << '\n';
			}
			else if (op == 4){
				cout << qpre(1, l, r, k) << '\n';
			}
			else if (op == 5){
				cout << qsuc(1, l, r, k) << '\n';
			}
		}
	}
	return 0;
}