#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 1500005

using namespace std;

const double A=0.756;

const int inf=;

int n,m,a[];

struct ScapeGoat_Tree

{

    ScapeGoat_Tree *ch[];

    int ex,cover,size,key;

    bool bad()

    {

        return cover*A<ch[]->cover||cover*A<ch[]->cover;

    }

    void pushup()

    {

        size=ch[]->size+ch[]->size+ex;

        cover=ch[]->cover+ch[]->cover+;

    }

}*null,pool[MAXN],*stack[MAXN],*lst[MAXN];

int top,len;

inline void Init()

{

   null=pool;

   null->cover=null->size=null->ex=null->key=;

   null->ch[]=null->ch[]=null;

   for(int i=;i<MAXN;i++)stack[++top]=pool+i;

}

inline ScapeGoat_Tree *New(int key)

{

   ScapeGoat_Tree *p=stack[top--];

   p->ch[]=p->ch[]=null;

   p->ex=p->cover=p->size=;

   p->key=key;

   return p;

}

struct Tree

{

    Tree *ch[];

    int l,r,mid;

    ScapeGoat_Tree *root;

    Tree(){ch[]=ch[]=NULL;root=null;}

    void* operator new(size_t size);

}*root,*C,*mempool;

void* Tree :: operator new(size_t size)

{

    if(C==mempool)

    {

       C=new Tree[(<<)+];

       mempool=C+(<<)+;

    }

    return C++;

}

void travel(ScapeGoat_Tree *p)

{

    if(p==null)return;

    travel(p->ch[]);

    if(p->ex) lst[++len]=p;

    else stack[++top]=p;

    travel(p->ch[]);

}

ScapeGoat_Tree *divide(int l,int r)

{

    if(l>r)return null;

    int mid=(l+r)>>;

    lst[mid]->ch[]=divide(l,mid-);

    lst[mid]->ch[]=divide(mid+,r);

    lst[mid]->pushup();

    return lst[mid];

}

ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key)

{

    if(p==null)

    {

       p=New(key);

       return &null;

    }

    p->size++;

    p->cover++;

    ScapeGoat_Tree **ret=insert(p->ch[p->key<=key],key);

    if(p->bad())ret=&p;

    return ret;

}

inline void rebuild(ScapeGoat_Tree *&p)

{

    len=;

    travel(p);

    p=divide(,len);

}

inline void Insert(ScapeGoat_Tree *&Root,int key)

{

    ScapeGoat_Tree **p=insert(Root,key);

    if(*p!=null)rebuild(*p);

}

inline int rank(ScapeGoat_Tree *p,int key)

{

    int ret=;

    while(p!=null)

     if(p->key>=key)

      p=p->ch[];

     else

      ret+=p->ch[]->size+p->ex,p=p->ch[];

    return ret;

}

void erase(ScapeGoat_Tree *p,int k)

{

    p->size--;

    if(p->ex&&k==p->ch[]->size+)

    {

        p->ex=;

        return;

    }

    if(p->ch[]->size>=k)

     erase(p->ch[],k);

    else erase(p->ch[],k-p->ch[]->size-p->ex);

}

inline void Erase_kth(ScapeGoat_Tree *&p,int k)

{

    erase(p,k);

    if(p->size<p->cover*A)rebuild(p);

}

inline void Erase(ScapeGoat_Tree *&p,int key)

{

    Erase_kth(p,rank(p,key)+);

}

void build(Tree *p)

{

    p->mid=(p->l+p->r)>>;

    if(p->l==p->r)return;

    p->ch[]=new Tree;

    p->ch[]->l=p->l;

    p->ch[]->r=p->mid;

    p->ch[]=new Tree;

    p->ch[]->l=p->mid+;

    p->ch[]->r=p->r;

    build(p->ch[]);

    build(p->ch[]);

}

void get_in(int key,int aim,Tree *p)

{

    Insert(p->root,key);

    if(p->l==p->r)return;

    if(aim<=p->mid)get_in(key,aim,p->ch[]);

    else get_in(key,aim,p->ch[]);

}

void get_rank(int l,int r,int key,Tree *p,int &ans)

{

    if(l<=p->l&&p->r<=r)

    {

        ans+=rank(p->root,key);

        return;

    }

    if(l<=p->mid)get_rank(l,r,key,p->ch[],ans);

    if(p->mid<r)get_rank(l,r,key,p->ch[],ans);

}

inline int Rank(int l,int r,int key)

{

    int ans=;

    get_rank(l,r,key,root,ans);

    return ans+;

}

inline int Kth(int l,int r,int rk)

{

    int z=,y=inf,mid;

    int ans=;

    while(z<=y)

    {

       mid=(z+y)>>;

       int k=Rank(l,r,mid);

       if(k<=rk)

         ans=mid,z=mid+;

       else

         y=mid-;

    }

    return ans;

}

void get_out(int aim,int key,Tree *p)

{

    Erase(p->root,key);

    if(p->l==p->r)return;

    if(aim<=p->mid)get_out(aim,key,p->ch[]);

    else get_out(aim,key,p->ch[]);

}

inline void work1()

{

    int l,r,k;

    scanf("%d%d%d",&l,&r,&k);

    printf("%d\n",Rank(l,r,k));

}

inline void work2()

{

    int l,r,k;

    scanf("%d%d%d",&l,&r,&k);

    printf("%d\n",Kth(l,r,k));

}

inline void work3()

{

    int aim,key;

    scanf("%d%d",&aim,&key);

    get_out(aim,a[aim],root);

    a[aim]=key;

    get_in(key,aim,root);

}

inline void work4()

{

    int l,r,k;

    scanf("%d%d%d",&l,&r,&k);

    printf("%d\n",Kth(l,r,Rank(l,r,k)-));

}

inline void work5()

{

    int l,r,k;

    scanf("%d%d%d",&l,&r,&k);

    printf("%d\n",Kth(l,r,Rank(l,r,k+)));

}

void dfs(Tree *p)

{

    if(p->l==p->r)return;

    dfs(p->ch[]);

    dfs(p->ch[]);

}

int main()

{

    freopen("psh.in","r",stdin);

    freopen("psh.out","w",stdout);

    Init();

    root=new Tree;

    root->l=;

    scanf("%d%d",&n,&m);

    root->r=n;

    build(root);

    dfs(root);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        get_in(a[i],i,root);

    }

    dfs(root);

    int opt;

    while(m--)

    {

        scanf("%d",&opt);

        switch(opt)

        {

            case :work1();break;

            case :work2();break;

            case :work3();break;

            case :work4();break;

            case :work5();break;

        }

    }

    return ;

}