#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
const int M = 5e4 + 1000;
struct node{
	int l, r, size, num, pri, val;
}tree[M*40];
int w[N], n, m, tot;
struct Treap{
	int root;
	void update(int p){
		tree[p].size = tree[tree[p].l].size + tree[tree[p].r].size + tree[p].num;
	}
	void zig(int &p){
		int q = tree[p].l;
		tree[p].l = tree[q].r;
		tree[q].r = p;
		tree[q].size = tree[p].size;
		update(p);
		p = q;
	}
	void zag(int &p){
		int q = tree[q].r;
		tree[p].r = tree[q].l;
		tree[q].l = p;
		tree[q].size = tree[p].size;
		update(p);
		p = q;
	}
	int newnode(int val){
		tree[++tot].val = val;
		tree[tot].pri = rand();
		tree[tot].num = tree[tot].size = 1;
		return tot;	
	}
	void Insert(int &p, int val){
		if(!p){
			p = newnode(val);
			return;
		}
		tree[p].size++;
		if(val == tree[p].val){
			tree[p].num++;
			return;		
		}
		else if(val < tree[p].val){
			Insert(tree[p].l, val);
			if(tree[tree[p].l].pri > tree[p].pri) zig(p);
		}
		else{
			Insert(tree[p].r, val);
			if(tree[tree[p].r].pri > tree[p].pri) zag(p);
		}
	}
	void Delete(int &p, int val){
		if(!p) return;
		tree[p].size--;
		if(tree[p].val == val){
			if(tree[p].num > 1){
				tree[p].num--;
				return;
			}
			if(!tree[p].l or !tree[p].r){
				p = tree[p].l + tree[p].r;
				return;
			}
			if(tree[tree[p].l].pri < tree[tree[p].r].pri){
				zag(p);
				Delete(tree[p].l, val);
			}
			else{
				zig(p);
				Delete(tree[p].r, val);
			}
			return;
		}
		if(tree[p].val < val) Delete(tree[p].r, val);
		else Delete(tree[p].l, val);
	}
	int GetPre(int val){
		int res = -1, p = root;
		while(p){
			if(tree[p].val < val){
				res = tree[p].val;
				p = tree[p].r;
			}
			else p = tree[p].l;
		}
		return res;
	}
	int GetNext(int val){
		int res = -1, p = root;
		while(p){
			if(tree[p].val > val){
				res = tree[p].val;
				p = tree[p].l;
			}
			else p = tree[p].r;
		}
		return res;
	}
	int GetValByRank(int p, int rank){
		if(!p) return -2147483647;
		if(tree[tree[p].l].size >= rank) return GetValByRank(tree[p].l, rank);
		if(tree[tree[p].l].size + tree[p].num >= rank) return tree[p].val;
		return GetValByRank(tree[p].r, rank - tree[tree[p].l].size - tree[p].num);
	}
	int GetRankByVal(int p, int val){
		if(!p) return 0;
		if(val == tree[p].val) return tree[tree[p].l].size + 1;
		if(val < tree[p].val) return GetRankByVal(tree[p].l, val);
		return GetRankByVal(tree[p].r, val) + tree[p].num + tree[tree[p].l].size;
	}
}tr[M << 2];
void build(int cur, int l, int r){
	for(int i = l; i <= r; i++)
		tr[cur].Insert(tr[cur].root, w[i]);
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(cur << 1, l, mid);
	build(cur << 1 | 1, mid + 1, r);	
}

int query_rank(int cur, int l, int r, int x, int y, int val){
	if(l > y or r < x) return 0;
	if(l >= x and r <= y) return tr[cur].GetRankByVal(tr[cur].root, val);
	int ret = 0;
	int mid = (l + r) >> 1;
	ret += query_rank(cur << 1, l, mid, x, y, val);
	ret += query_rank(cur << 1 | 1, mid + 1, r, x, y, val);
	return ret;
}

int query_val(int x, int y, int rank){
	int l = 0, r = 2147483647, mid, ans = -1;
	while(l <= r){
		mid = (l + r) >> 1;
		if(query_rank(1, 1, n, x, y, mid) + 1 <= rank) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}

void update(int cur, int l, int r, int x, int val){
	if(l > x or r < x) return;
	tr[cur].Delete(tr[cur].root, w[x]);
	tr[cur].Insert(tr[cur].root, val);
	if(l == r) return;
	int mid = (l + r) >> 1;
	update(cur << 1, l, mid, x, val);
	update(cur << 1 | 1, mid + 1, r, x, val);
}

int query_pre(int cur, int l, int r, int x, int y, int val){
	if(l > y or r < x) return -2147483647;
	if(l >= x and r <= y) return tr[cur].GetPre(val);
	int mid = (l + r) >> 1;
	return max(query_pre(cur << 1, l, mid, x, y, val), query_pre(cur << 1 | 1, mid + 1, r, x, y, val));
}

int query_next(int cur, int l, int r, int x, int y, int val){
	if(l > y or r < x) return 2147483647;
	if(l >= x and r <= y) return tr[cur].GetNext(val);
	int mid = (l + r) >> 1;
	return min(query_next(cur << 1, l, mid, x, y, val), query_next(cur << 1 | 1, mid + 1, r, x, y, val));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> w[i];	
	build(1, 1, n);
	int opt, l, r, k;
	for(int i = 1; i <= m; i++){
		cin >> opt;
		if(opt == 1) {
			cin >> l >> r >> k;
			cout << query_rank(1, 1, n, l, r, k) + 1 << "\n";
		}
		else if(opt == 2){
			cin >> l >> r >> k;
			cout << query_val(l, r, k) << "\n";
		}
		else if(opt == 3){
			cin >> l >> k;
			update(1, 1, n, l, k);
			w[l] = k;
		}
		else if(opt == 4){
			cin >> l >> r >> k;
			cout << query_pre(1, 1, n, l, r, k) << "\n";
		}
		else if(opt == 5){
			cin >> l >> r >> k;
			cout << query_next(1, 1, n, l, r, k) << "\n";
		}
	}	
}