/**************************************************************    Problem: 3196    User: BeiYu    Language: C++    Result: Accepted    Time:6828 ms    Memory:57552 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; #define debug(a) cout<<(#a)<<"="<<a<<" "#define uor(i,j,k) for(int i=j;i<=(int)k;i++)#define uep(i,j,k) for(int i=j;i<(int)k;i++)#define dor(i,j,k) for(int i=j;i>=(int)k;i--) typedef long long ll;typedef pair<int,int> pr;typedef vector<int> vi;typedef vector<ll> vl;typedef vector<string> vs;const int N = 1600050;const int M = 25;const int oo = 0x3fffffff;const ll  OO = 1e18; const ll p = 1000000007;ll Pow(ll a,ll b,ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }ll Pow(ll a,ll b,ll p,ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }ll inv(ll x) { return Pow(x,p-2); }void Add(ll &x,ll y) { x=(x+y%p)%p; }void Sub(ll &x,ll y) { x=(x-y%p+p)%p; }void Mul(ll &x,ll y) { x=x*(y%p)%p; }int chkmax(ll &x,ll y) { return x<y?x=y,1:0; }int chkmin(ll &x,ll y) { return x>y?x=y,1:0; } inline ll in(ll x=0,char ch=getchar(),int v=1) {    while(ch>‘9‘ || ch<‘0‘) v=ch==‘-‘?-1:v,ch=getchar();    while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();    return x*v;}/*end*/ int n,m;int a[N]; namespace Treap {    #define lc(o) ch[o][0]    #define rc(o) ch[o][1]    int cp;         int sz[N],ss[N],ch[N][2],f[N],rv[N];    int val[N];         int Newnode(int v) {        ++cp,ss[cp]=sz[cp]=1,f[cp]=lc(cp)=rc(cp)=0,val[cp]=v,rv[cp]=rand();        return cp;    }    void init() { rv[0]=-oo; }    void Update(int o) { sz[o]=sz[lc(o)]+sz[rc(o)]+ss[o]; }    void Rot(int &o,int d) {        int t=ch[o][d];ch[o][d]=ch[t][d^1],ch[t][d^1]=o,Update(o),Update(t),o=t;    }    void insert(int &o,int v) {        if(!o) { o=Newnode(v);return; }        if(val[o]==v) { ss[o]++,Update(o);return; }        int d=v>val[o];        insert(ch[o][d],v);        if(rv[ch[o][d]]>rv[o]) Rot(o,d);        else Update(o);    }    void earse(int &o,int v) {        if(val[o]==v) {            if(ss[o]>1) { ss[o]--,Update(o);return; }            int d=rv[lc(o)]<rv[rc(o)];            if(!ch[o][d]) { o=0;return; }            Rot(o,d),earse(ch[o][d^1],v);        }else earse(ch[o][v>val[o]],v);        Update(o);    }    int rk(int o,int v) {        if(!o) return 0;        if(val[o]<v) return sz[lc(o)]+ss[o]+rk(rc(o),v);        else if(val[o]>v) return rk(lc(o),v);        else return sz[lc(o)];    }    int kth(int o,int k) {        if(sz[lc(o)]>=k) return kth(lc(o),k);        else if(sz[lc(o)]+ss[o]<k) return kth(rc(o),k-sz[lc(o)]-ss[o]);        else return val[o];    }    int pre(int o,int v) {        if(!o) return -oo;        if(val[o]>=v) return pre(lc(o),v);        else return max(val[o],pre(rc(o),v));    }    int nxt(int o,int v) {        if(!o) return oo;        if(val[o]<=v) return nxt(rc(o),v);        else return min(val[o],nxt(lc(o),v));    }         #undef lc    #undef rc}; namespace Seg {    #define lc (o<<1)    #define rc (o<<1|1)    #define mid ((l+r)>>1)         int rt[N];         void Build(int o,int l,int r) {        uor(i,l,r) Treap::insert(rt[o],a[i]);        if(l==r) return;        Build(lc,l,mid),Build(rc,mid+1,r);    }    int rk(int o,int l,int r,int L,int R,int v) {        if(L<=l && r<=R) return Treap::rk(rt[o],v);        int res=0;        if(L<=mid) res+=rk(lc,l,mid,L,R,v);        if(R>mid) res+=rk(rc,mid+1,r,L,R,v);        return res;    }    int kth(int L,int R,int k) {        int l=-oo,r=oo;        while(l<=r) {            if(rk(1,1,n,L,R,mid)<k) l=mid+1;            else r=mid-1;        }return l-1;    }    void Motify(int o,int l,int r,int x,int x1,int x2) {        Treap::earse(rt[o],x1),Treap::insert(rt[o],x2);        if(l==r) return;        if(x<=mid) Motify(lc,l,mid,x,x1,x2);        else Motify(rc,mid+1,r,x,x1,x2);    }    int pre(int o,int l,int r,int L,int R,int x) {        if(L<=l && r<=R) return Treap::pre(rt[o],x);        int res=-oo;        if(L<=mid) res=max(res,pre(lc,l,mid,L,R,x));        if(R>mid) res=max(res,pre(rc,mid+1,r,L,R,x));        return res;    }    int nxt(int o,int l,int r,int L,int R,int x) {        if(L<=l && r<=R) return Treap::nxt(rt[o],x);        int res=oo;        if(L<=mid) res=min(res,nxt(lc,l,mid,L,R,x));        if(R>mid) res=min(res,nxt(rc,mid+1,r,L,R,x));        return res;    }         #undef lc    #undef rc    #undef mid} int main() {    n=in(),m=in();    uor(i,1,n) a[i]=in();    Treap::init();    Seg::Build(1,1,n);    for(;m--;) {        int opt=in(),l,r,k;        switch(opt) {            case 1:l=in(),r=in(),k=in(),printf("%d\n",Seg::rk(1,1,n,l,r,k)+1);break;            case 2:l=in(),r=in(),k=in(),printf("%d\n",Seg::kth(l,r,k));break;            case 3:l=in(),r=in(),Seg::Motify(1,1,n,l,a[l],r),a[l]=r;break;            case 4:l=in(),r=in(),k=in(),printf("%d\n",Seg::pre(1,1,n,l,r,k));break;            default:l=in(),r=in(),k=in(),printf("%d\n",Seg::nxt(1,1,n,l,r,k));break;        }    }return 0;}