#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int N = 4e7+10;
const int inf = 1e9;
#define mid (l+r>>1)
int n,m,a[maxn];

int id,root[maxn],ls[N],rs[N],sum[N],rt1[N],rt2[N];
int li[maxn],top;
int lowbit(int x){ return x&(-x); }
void get_point(int l,int r)
{
	rt1[0] = rt2[0] = 0;
	for(int i=l-1;i;i-=lowbit(i) )	rt1[++rt1[0]] = root[i];
	for(int i=r;i;i-=lowbit(i) )	rt2[++rt2[0]] = root[i];
}
void rt_left()
{
	for(int i=1;i<=rt1[0];i++)	rt1[i] = ls[rt1[i]];
	for(int i=1;i<=rt2[0];i++)	rt2[i] = ls[rt2[i]];
}
void rt_right()
{
	for(int i=1;i<=rt1[0];i++)	rt1[i] = rs[rt1[i]];
	for(int i=1;i<=rt2[0];i++)	rt2[i] = rs[rt2[i]];
}
void update_sgt(int &rt,int l,int r,int pos,int val)
{
	if( !rt )	rt = ++id;
	if( l==r )	{ sum[rt] += val; return; }
	if( pos<=mid )	update_sgt(ls[rt],l,mid,pos,val);
	else	update_sgt(rs[rt],mid+1,r,pos,val );
	sum[rt] = sum[ls[rt]]+sum[rs[rt]];
}
int ask_sgt_sum(int l,int r,int L,int R)
{
	if( l>R || r<L )	return 0;
	if( l>=L && r<=R )
	{
		int temp = 0;
		for(int i=1;i<=rt1[0];i++)	temp -= sum[rt1[i]];
		for(int i=1;i<=rt2[0];i++)	temp += sum[rt2[i]];
		return temp; 
	}
	int rt3[109],rt4[109];
	for(int i=0;i<=rt1[0];i++)	rt3[i] = rt1[i];
	for(int i=0;i<=rt2[0];i++)	rt4[i] = rt2[i];			
	rt_left();
	int x = ask_sgt_sum(l,mid,L,R);
	for(int i=1;i<=rt1[0];i++)	rt1[i] = rt3[i];
	for(int i=1;i<=rt2[0];i++)	rt2[i] = rt4[i];
	rt_right();
	return x+ask_sgt_sum(mid+1,r,L,R);	
}
int k_th(int l,int r,int k)
{
	if( l==r )
	{
		int temp = 0;
		for(int i=1;i<=rt1[0];i++)	temp -= sum[rt1[i]];
		for(int i=1;i<=rt2[0];i++)	temp += sum[rt2[i]];
		if( temp<k )	return inf;
		else	return l;		
	}
	int x = 0;
	for(int i=1;i<=rt1[0];i++)	x -= sum[ls[rt1[i]]];
	for(int i=1;i<=rt2[0];i++)	x += sum[ls[rt2[i]]];
	if(  k<=x )
	{
		rt_left();
		return k_th(l,mid,k);
	}
	else
	{
		rt_right();
		return k_th(mid+1,r,k-x );
	}
}
int prek_th(int l,int r,int k)
{	
	get_point(l,r);
	int kth = ask_sgt_sum(0,inf,0,k-1);//小于等于k-1的数字有多少个
	if( kth==0 )	return inf;
	get_point(l,r);
	int res = k_th(0,inf,kth);
	return res; 
}
int sufk_th(int l,int r,int k)
{
	get_point(l,r);
	int kth = ask_sgt_sum(0,inf,0,k)+1;
	get_point(l,r);
	int res = k_th( 0,inf,kth );
	return res;
}

void update_BIT(int x,int val,int zhi)//把x位置,在权值线段树上的val位置修改zhi  
{
	for(int i=x;i<=n;i+=lowbit(i) )	
		update_sgt( root[i],0,inf,val,zhi );
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i] ),li[i] = a[i];
	
	for(int i=1;i<=n;i++)	update_BIT( i,a[i],1 );	
	for(int i=1;i<=m;i++)
	{
		int type,pos,l,r,k; scanf("%d",&type );
		if( type==1 )
		{
			scanf("%d%d%d",&l,&r,&k );
			get_point(l,r);//获取区间的权值线段树
			printf("%d\n",ask_sgt_sum(0,inf,0,k-1)+1 );	
		}
		else if( type==2 )
		{
			scanf("%d%d%d",&l,&r,&k );
			get_point(l,r);//获取区间的权值线段树
			printf("%d\n",k_th(0,inf,k) );			
		}
		else if( type==3 )
		{
			scanf("%d%d",&pos,&k );
			update_BIT( pos,a[pos],-1 );
			a[pos] = k;
			update_BIT( pos,a[pos],1 );
		}
		else if( type==4 )
		{
			scanf("%d%d%d",&l,&r,&k );
			int res = prek_th(l,r,k);
			if( res==inf )	printf("-2147483647\n");
			else	printf("%d\n",res );
		}
		else if( type==5 )
		{
			scanf("%d%d%d",&l,&r,&k );		
			int res = sufk_th(l,r,k);
			if( res==inf )	printf("2147483647\n");
			else	printf("%d\n",res );
		}
	}
}