#include<cstdio>
#include<map>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
using namespace std;
int n,m,cnt,root[4000001],a[1000001];
struct treap
{
	int rnd,w,num,size,ch[2];
}t[8000001];
void pushup(int x)
{
	t[x].size=t[x].num+t[t[x].ch[0]].size+t[t[x].ch[1]].size;
}
void rotate(int &rt,int x)
{
	int y=t[rt].ch[x];
	t[rt].ch[x]=t[y].ch[x^1];
	t[y].ch[x^1]=rt;
	pushup(rt);
	pushup(y);
	rt=y;
}
void insert(int &rt,int k)
{
	if(!rt)
	{
		rt=++cnt;
		t[rt].w=k;
		t[rt].num=t[rt].size=1;
		t[rt].rnd=rand();
		return;
	}
	if(t[rt].w==k)
	{
		t[rt].num++;
		return;
	}
	else if(t[rt].w>k)
	{
		insert(t[rt].ch[0],k);
		if(t[t[rt].ch[0]].rnd>t[rt].rnd)
		{
			rotate(rt,0);
		}
	}
	else
	{
		insert(t[rt].ch[1],k);
		if(t[t[rt].ch[1]].rnd>t[rt].rnd)
		{
			rotate(rt,1);
		}
	}
	pushup(rt);
}
void del(int &rt,int k)
{
	if(t[rt].w>k)
	{
		del(t[rt].ch[0],k);
	}
	else if(t[rt].w<k)
	{
		del(t[rt].ch[1],k);
	}
	else
	{
		if(t[rt].num>1)
		{
			t[rt].num--;
			return;
		}
		else if(t[rt].ch[0]*t[rt].ch[1]==0)
		{
			rt=t[rt].ch[0]+t[rt].ch[1];
		}
		else
		{
			if(t[t[rt].ch[0]].rnd>t[t[rt].ch[1]].rnd)
			{
				rotate(rt,0);
				del(t[rt].ch[1],k);
			}
			else
			{
				rotate(rt,1);
				del(t[rt].ch[0],k);
			}
		}
	}
	pushup(rt);
}
void build(int l,int r,int rt)
{
	for(int i=l;i<=r;i++)
	{
		insert(root[rt],a[i]);
	}
	if(l!=r)
	{
		int mid=(l+r)>>1;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
	}
}
void change(int l,int r,int rt,int x,int k)
{
	del(root[rt],a[x]);
	insert(root[rt],k);
	if(l==r)
	{
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		change(l,mid,rt<<1,x,k);
	}
	else
	{
		change(mid+1,r,rt<<1|1,x,k);
	}
}
int find(int rt,int k)
{
	if(!rt)
	return 0;
	else if(t[rt].w==k)
	return t[t[rt].ch[0]].size;
	else if(t[rt].w>k)
	return find(t[rt].ch[0],k);
	else
	return t[t[rt].ch[0]].size+t[rt].num+find(t[rt].ch[1],k);
}
int ask(int l,int r,int rt,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		return find(root[rt],k);
	}
	int mid=(l+r)>>1;
	int ans=0;
	if(L<=mid)
	{
		ans+=ask(l,mid,rt<<1,L,R,k);
	}
	if(R>mid)
	{
		ans+=ask(mid+1,r,rt<<1|1,L,R,k);
	}
	return ans;
}
int ask1(int L,int R,int k)
{
	int l=0,r=1e8;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(ask(1,n,1,L,R,mid)<k)
		{
			l=mid;
		}
		else
		{
			r=mid-1;
		}
	}
	return r;
}
int ans;
void up(int rt,int k)
{
	if(!rt)
	return;
	if(t[rt].w>=k)
	{
		up(t[rt].ch[0],k);
	}
	else
	{
		ans=max(ans,t[rt].w);
		up(t[rt].ch[1],k);
	}
}
void down(int rt,int k)
{
	if(!rt)
	return;
	if(t[rt].w<=k)
	{
		down(t[rt].ch[1],k);
	}
	else
	{
		ans=min(ans,t[rt].w);
		down(t[rt].ch[0],k);
	}
}
void high(int l,int r,int rt,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		up(root[rt],k);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
	{
		high(l,mid,rt<<1,L,R,k);
	}
	if(R>mid)
	{
		high(mid+1,r,rt<<1|1,L,R,k);
	}
}
void low(int l,int r,int rt,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		down(root[rt],k);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
	{
		low(l,mid,rt<<1,L,R,k);
	}
	if(R>mid)
	{
		low(mid+1,r,rt<<1|1,L,R,k);
	}
}
int main()
{
//	srand((unsigned)time(NULL));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&a[i]);
    }
    build(1,n,1);
    while(m--)
    {
    	int x,y,z,k;
    	scanf("%d%d%d",&x,&y,&z);
    	switch(x)
    	{
    		case 1:
    			scanf("%d",&k);
    			printf("%d\n",ask(1,n,1,y,z,k)+1);
    			break;
	  		case 2:
    			scanf("%d",&k);
    			printf("%d\n",ask1(y,z,k));
    			break;
    		case 3:
    			change(1,n,1,y,z);
				a[y]=z;
    			break;
    		case 4:
    			scanf("%d",&k);
    			ans=-2147483647;
    			high(1,n,1,y,z,k);
    			printf("%d\n",ans);
    			break;
    		case 5:
    			scanf("%d",&k);
    			ans=2147483647;
    			low(1,n,1,y,z,k);
    			printf("%d\n",ans);
    			break;
    	}
    }
    return 0;
}