#include<bits/stdc++.h>
#define ri register int
#define il inline
#define MD ri md=l+r>>1
#define lc l,md
#define rc md+1,r
using namespace std;
int rt,n,m,cn,cnt,a[50005],tr[800005],sm[21000005],ls[21000005],rs[21000005],Ls[800005],Rs[800005];
il void add(int &x,ri l,ri r,ri y,ri z){
	if(z==1&&!x)x=++cnt;if(x)sm[x]+=z;if(!x||l==r)return;
	MD;if(y<=md)add(ls[x],lc,y,z);else add(rs[x],rc,y,z);
}
il int qr(ri x,ri l,ri r,ri L,ri R){
	if(!x)return 0;if(L<=l&&r<=R)return sm[x];MD;
	return (L<=md?qr(ls[x],lc,L,R):0)+(R>md?qr(rs[x],rc,L,R):0);
}
il int rk(ri x,ri l,ri r,ri s,ri t,ri L,ri R){
	if(!x)return 0;if(s<=l&&r<=t)return qr(tr[x],1,n,L,R);MD;
	return (s<=md?rk(Ls[x],lc,s,t,L,R):0)+(t>md?rk(Rs[x],rc,s,t,L,R):0);
}
il int kth(ri x,ri l,ri r,ri k,ri L,ri R){
	if(l==r)return l;MD,y=qr(tr[Ls[x]],1,n,L,R);
	return (k<=y)?kth(Ls[x],lc,k,L,R):kth(Rs[x],rc,k-y,L,R);
}
il void upd(int &x,ri l,ri r,ri ps,ri y,ri z){
	if(z==1&&!x)x=++cn;if(x)add(tr[x],1,n,y,z);if(!x||l==r)return;
	MD;(ps<=md)?upd(Ls[x],lc,ps,y,z):upd(Rs[x],rc,ps,y,z);
}
int main(){
	scanf("%d%d",&n,&m);
	for(ri i=1;i<=n;++i)scanf("%d",&a[i]),upd(rt,0,1e8,a[i],i,1);
	for(ri op,x,y,z;m--;){
		scanf("%d%d%d",&op,&x,&y);
		if(op!=3){
			scanf("%d",&z);
			printf("%d\n",op<3?(op==1?rk(rt,0,1e8,0,z-1,x,y)+1:kth(rt,0,1e8,z,x,y)):
			(op==4?(rk(rt,0,1e8,0,z-1,x,y)==rk(rt,0,1e8,0,-1e9,x,y)?-2147483647:kth(rt,0,1e8,rk(rt,0,1e8,0,z-1,x,y),x,y)):
			(rk(rt,0,1e8,0,z,x,y)==rk(rt,0,1e8,0,1e9,x,y)?2147483647:kth(rt,0,1e8,rk(rt,0,1e8,0,z,x,y)+1,x,y))));
		}else upd(rt,0,1e8,a[x],x,-1),upd(rt,0,1e8,y,x,1),a[x]=y;
	}
	return 0;
}

空间开少RE，开大MLE