/*1.AC:tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+tr[k].w;
WA:tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
2.AC:tmp=max(tr[k].v,tmp);
WA:tmp=max(tr[k].v,num);
3.AC:if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
WA:if(tr[k].l*tr[k].r==0)k=tr[k].l*tr[k].r;
*/
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define inf 100000000
#define M 3000001
#define N 200001
using namespace std;
struct data{
int l,r,s,v,w,rnd;
}tr[M];
int n,m,sz,tmp,a[N],root[N];
void update(int k){
tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+tr[k].w;
}
void lturn(int &k){
int t=tr[k].r;
tr[k].r=tr[t].l;
tr[t].l=k;
tr[t].s=tr[k].s;
update(k);
k=t;
}
void rturn(int &k){
int t=tr[k].l;
tr[k].l=tr[t].r;
tr[t].r=k;
tr[t].s=tr[k].s;
update(k);
k=t;
}
void insert(int &k,int num){
if(!k){
k=++sz;
tr[k].s=tr[k].w=1;
tr[k].v=num;tr[k].rnd=rand();
return;
}
tr[k].s++;
if(num==tr[k].v)tr[k].w++;
else if(num<tr[k].v){
insert(tr[k].l,num);
if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
}
else{
insert(tr[k].r,num);
if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
}
}
void del(int &k,int num){
if(tr[k].v==num){
if(tr[k].w>1){
tr[k].w--;
tr[k].s--;
return;
}
if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd){
rturn(k);
del(k,num);
}
else{
lturn(k);
del(k,num);
}
}
else if(num<tr[k].v){
del(tr[k].l,num);
tr[k].s--;
}
else{
del(tr[k].r,num);
tr[k].s--;
}
}
void build(int k,int l,int r,int x,int num){
insert(root[k],num);
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)build(k<<1,l,mid,x,num);
else build(k<<1|1,mid+1,r,x,num);
}
void ask_rank(int k,int num){
if(!k)return;
if(num==tr[k].v){
tmp+=tr[tr[k].l].s;
return;
}
else if(num<tr[k].v)ask_rank(tr[k].l,num);
else{
tmp+=tr[tr[k].l].s+tr[k].w;
ask_rank(tr[k].r,num);
}
}
void get_rank(int k,int l,int r,int x,int y,int num){
if(l==x&&r==y){
ask_rank(root[k],num);
return;
}
int mid=(l+r)>>1;
if(y<=mid)get_rank(k<<1,l,mid,x,y,num);
else if(x>mid)get_rank(k<<1|1,mid+1,r,x,y,num);
else{
get_rank(k<<1,l,mid,x,mid,num);
get_rank(k<<1|1,mid+1,r,mid+1,y,num);
}
}
void get_index(int x,int y,int z){
int l=0,r=inf,ans;
while(l<=r){
int mid=(l+r)>>1;
tmp=1;get_rank(1,1,n,x,y,mid);
if(tmp<=z){
l=mid+1;ans=mid;
}
else r=mid-1;
}
printf("%d\n",ans);
}
void change(int k,int l,int r,int x,int num,int y){
del(root[k],y);
insert(root[k],num);
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)change(k<<1,l,mid,x,num,y);
else change(k<<1|1,mid+1,r,x,num,y);
}
void before(int k,int num)
{
if(!k)return;
if(tr[k].v<num){
tmp=max(tr[k].v,tmp);
before(tr[k].r,num);
}
else before(tr[k].l,num);
}
void after(int k,int num)
{
if(!k)return;
if(tr[k].v>num){
tmp=min(tr[k].v,tmp);
after(tr[k].l,num);
}
else after(tr[k].r,num);
}
void ask_after(int k,int l,int r,int x,int y,int num)
{
if(l==x&&r==y){after(root[k],num);return;}
int mid=(l+r)>>1;
if(mid>=y)ask_after(k<<1,l,mid,x,y,num);
else if(mid<x)ask_after(k<<1|1,mid+1,r,x,y,num);
else
{
ask_after(k<<1,l,mid,x,mid,num);
ask_after(k<<1|1,mid+1,r,mid+1,y,num);
}
}
void ask_before(int k,int l,int r,int x,int y,int num)
{
if(l==x&&r==y){before(root[k],num);return;}
int mid=(l+r)>>1;
if(mid>=y)ask_before(k<<1,l,mid,x,y,num);
else if(mid<x)ask_before(k<<1|1,mid+1,r,x,y,num);
else
{
ask_before(k<<1,l,mid,x,mid,num);
ask_before(k<<1|1,mid+1,r,mid+1,y,num);
}
}
int main(){
//srand(time(0));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)build(1,1,n,i,a[i]);
for(int i=1;i<=m;i++)
{
int f;scanf("%d",&f);
int x,y,k;
switch(f)
{
case 1:scanf("%d%d%d",&x,&y,&k);tmp=1;get_rank(1,1,n,x,y,k);printf("%d\n",tmp);break;
case 2:scanf("%d%d%d",&x,&y,&k);get_index(x,y,k);break;
case 3:scanf("%d%d",&x,&y);change(1,1,n,x,y,a[x]);a[x]=y;break;
case 4:scanf("%d%d%d",&x,&y,&k);tmp=0;ask_before(1,1,n,x,y,k);printf("%d\n",tmp);break;
case 5:scanf("%d%d%d",&x,&y,&k);tmp=inf;ask_after(1,1,n,x,y,k);printf("%d\n",tmp);break;
}
}
return 0;
}