#include<bits/stdc++.h>
#define lv x<<1
#define rv x<<1|1
using namespace std;
const int maxn = 3e6 + 5;
const int inf = 2147483647;
int n,m,a[maxn],opt,num;
int val[maxn],l[maxn],r[maxn],size[maxn],rnd[maxn],tot;
struct fhq_treap {
	int root,cl,cr;
	void pushup(int x) {
		size[x] = size[l[x]] + size[r[x]] + 1;
	}
	int newnode(int x) {
		val[++tot] = x;
		size[tot] = 1;
		l[tot] = r[tot] = 0;
		rnd[tot] = rand();
		return tot;
	}
	void split(int k,int &x,int &y,int v) {
		if(!k) {
			x = y = 0; return;
		}
		if(val[k] <= v) x = k,split(r[x],r[x],y,v);
		else y = k,split(l[y],x,l[y],v);
		pushup(k);
	}
	int merge(int x,int y) {
		if(!x || !y) return x + y;
		if(rnd[x] < rnd[y]) {
			r[x] = merge(r[x],y);
			pushup(x); return x;
		} else {
			l[y] = merge(x,l[y]);
			pushup(y); return y;
		}
	}
	void insert(int x) {
		int ls,rs;
		split(root,ls,rs,x);
		root = merge(merge(ls,newnode(x)),rs);
	}
	void del(int x) {
		int ls,rs,ll,rr;
		split(root,ls,rs,x);
		split(ls,ll,rr,x - 1);
		rr = merge(l[rr],r[rr]);
		root = merge(merge(ll,rr),rs);
	}
	int query_rnk(int x) {
		int ls,rs;
		split(root,ls,rs,x - 1);
		int tmp = size[ls] + 1;
		root = merge(ls,rs);
		return tmp;
	}
	int query_kth(int x,int k) {
		int p = size[l[x]] + 1;
		if(p == k)return val[x];
		if(p < k)return query_kth(r[x],k - p);
		else query_kth(l[x],k);
	}
	int query_pre(int x) {
		int ls,rs;
		split(root,ls,rs,x - 1);
		int tmp;
		if(size[ls]) 
			tmp = query_kth(ls,size[ls]);
		else 
			tmp = -inf;
		root = merge(ls,rs);
		return tmp;
	}
	int query_sub(int x) {
		int ls,rs;
		split(root,ls,rs,x);
		int tmp;
		if(size[rs]) 
			tmp = query_kth(rs,1);
		else 
			tmp = inf;
		root = merge(ls,rs);
		return tmp;
	}
}tree[maxn<<2];
void build(int x,int l,int r) {
	tree[x].cl = l;tree[x].cr = r;
	for(int i = l;i <= r;++i)
		tree[x].insert(a[i]);
	if(l == r) return;
	int mid = (l + r)>>1;
	build(lv,l,mid); build(rv,mid + 1,r);
}
void modify(int x,int p,int k) {
	tree[x].del(a[p]);
	tree[x].insert(k);
	if(tree[x].cl == tree[x].cr) return;
	int mid = (tree[x].cl + tree[x].cr)>>1;
	if(mid >= p) modify(lv,p,k);
	else modify(rv,p,k);
}
int seg_rnk(int x,int l,int r,int k) {
	if(tree[x].cl > r || tree[x].cr < l)
		return 0;
	if(tree[x].cl >= l && tree[x].cr <= r) 
		return tree[x].query_rnk(k) - 1;
	else 
		return seg_rnk(lv,l,r,k) + seg_rnk(rv,l,r,k);
}
int seg_kth(int l,int r,int k) {
	int x = 0,y = 1e8,mid,ans;
	while(x <= y) {
		mid = (x + y)>>1;
		if(seg_rnk(1,l,r,mid) < k)
			x = mid + 1,ans = mid;
		else 
			y = mid - 1;
	}
	return ans;
}
int seg_pre(int x,int l,int r,int k) {
	if(tree[x].cl > r || tree[x].cr < l)
		return -inf;
	if(tree[x].cl >= l && tree[x].cr <= r)
		return tree[x].query_pre(k);
	return max(seg_pre(lv,l,r,k) , seg_pre(rv,l,r,k));
}
int seg_sub(int x,int l,int r,int k) {
	if(tree[x].cl > r || tree[x].cr < l)
		return inf;
	if(tree[x].cl >= l && tree[x].cr <= r)
		return tree[x].query_sub(k);
	return min(seg_sub(lv,l,r,k) , seg_sub(rv,l,r,k));
}
signed main(int argc , char const *argv[]) {
//	freopen("P3380_1.in","r",stdin);
	srand(time(NULL));
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i <= n;++i) cin>>a[i];
	build(1,1,n);
	int lk,rk,kk,pos;
	for(int i = 1;i <= m;++i) {
		cin>>opt;
		if(opt == 3) {
			cin>>pos>>kk;
			modify(1,pos,kk);
			a[pos] = kk;
		} else {
			cin>>lk>>rk>>kk;
			if(opt == 1) cout<<seg_rnk(1,lk,rk,kk) + 1<<'\n';
			if(opt == 2) cout<<seg_kth(lk,rk,kk)<<'\n';
			if(opt == 4) cout<<seg_pre(1,lk,rk,kk)<<'\n';
			if(opt == 5) cout<<seg_sub(1,lk,rk,kk)<<'\n';
		}
	}
	return 0;
}