#include<bits/stdc++.h>
#define N 50009
#define inf 2147483647
using namespace std;
const int maxn = 1e8;
int n,m,head[N<<5],s[N<<5],ls[N<<5],rs[N<<5],tot=1;
int ch[N<<9][2],val[N<<9],key[N<<9],siz[N<<9],total,splx,sply,splz;
void upd(int now) {
	siz[now] = siz[ch[now][0]] + siz[ch[now][1]] + 1;
}
void split(int now,int k,int &x,int &y) {
	if(!now) x = y = 0;
	else {
		if(val[now] <= k) x = now , split(ch[now][1],k,ch[now][1],y);
		else y = now , split(ch[now][0],k,x,ch[now][0]);
		upd(now); 
	}
}
int merge(int x,int y) {
	if(!x||!y) return x+y;
	if(key[x] > key[y]) {
		ch[x][1] = merge(ch[x][1],y);
		return x;
	} 
	else {
		ch[y][0] = merge(x,ch[y][0]);
		return y;
	}
}
int new_node(int value) {
	++total,val[total] = value , siz[total] = 1 ,key[total] = rand();
	return total;
}
int findl(int id) {
	if(ls[id] == 0) ++tot,ls[id] = tot;
	return ls[id];
}
int findr(int id) {
	if(rs[id] == 0) ++tot,rs[id] = tot;
	return rs[id];
}
void add(int L,int R,int now,int id,int k,int flag) {
	int mid = (L+R)/2;
	if(flag) split(head[id],k-1,splx,sply),head[id]=merge(splx,merge(new_node(k),sply));
	else split(head[id],k-1,splx,sply),split(sply,k,sply,splz),head[id]=merge(splx,splz);
	if(L==R) return;
	else if(now<=mid) add(L,mid,now,findl(id),k,flag);
	else add(mid+1,R,now,findr(id),k,flag);
} 
int kth(int L,int R,int now,int id,int l,int r) {
	int mid = (L+R)/2,aans;
	if(L==R) return 1;
	else if(now <= mid) return kth(L,mid,now,findl(id),l,r);
	if(!ls[id]) return kth(mid+1,R,now,findr(id),l,r);
	split(head[ls[id]],r,splx,sply),split(splx,l-1,splx,splz),aans=siz[splz];
	head[ls[id]] = merge(merge(splx,splz),sply);
	return aans+kth(mid+1,R,now,findr(id),l,r);
}
int ukth(int L,int R,int id,int now,int l,int r) {
	int mid = (L+R)/2,aans;
	if(L==R) return L;
	if(!ls[id]) return ukth(mid+1,R,findr(id),now,l,r);
	split(head[ls[id]],r,splx,sply),split(splx,l-1,splx,splz),aans=siz[splz];
	head[ls[id]] = merge(merge(splx,splz),sply);
	if(now>aans) return ukth(mid+1,R,findr(id),now-aans-1,l,r);
	else return ukth(L,mid,findl(id),now,l,r);
}
int main() {
	int opt,l,r,k,emm;
	srand(1919810);
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++) scanf("%d",&s[i]),add(1,n,s[i],1,i,1);
	while(m--) {
		scanf("%d%d%d",&opt,&l,&r);
		if(opt == 1) scanf("%d",&k),printf("%d\n",kth(1,n,k,1,l,r));
		else if(opt == 2) scanf("%d",&k),printf("%d\n",ukth(1,n,1,k,l,r));
		else if(opt == 3) add(1,n,s[l],1,l,0),s[l]=r,add(1,n,s[l],1,l,1);
		else {
			scanf("%d",&k),emm = kth(1,n,k,1,l,r);
			if(opt == 4) printf("%d\n",emm==1?-inf:ukth(1,n,1,emm-1,l,r));
			else printf("%d\n",emm==n+1?inf:ukth(1,n,1,emm,l,r));
		}
	}
	return 0;
}