#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
#define cnt(x) t[x].cnt
#define size(x) t[x].size
#define fa(x) t[x].fa
#define val(x) t[x].val
int tot,root[maxn],a[maxn],n,T;
struct Tree
{
    int ch[2],  cnt,size,  fa;
    long long val;
}t[maxn*5];
struct lineTree
{
    int l,r;
    long long w;
}tree[maxn];
int ff(int x)
{
    return x == rs( fa(x) );
}
void connect(int x,int y,int now)
{
    t[y].ch[now] = x;
    fa(x) = y;
}
void update(int x)
{
    size(x) = size(ls(x)) + size(rs(x)) + cnt(x);
}
void rotate(int x)
{
    int y = fa(x) , z = fa(y);
    int fx = ff(x);
    int fy = ff(y);
    connect( t[x].ch[fx^1] ,y,fx);
    connect(y,x, fx^1 );
    connect(x,z,fy);
    update(y);update(x);
}
void splay(int x,int y,int q)
{
    y = fa(y);
    while(	fa(x) != y	){
        if( fa(fa(x))  ==  y ) rotate(x);
        else if( ff(x) == ff(fa(x)) ) rotate( fa(x) ),rotate(x);
        else rotate(x),rotate(x);
    }
    if(y == 0) root[q] = x;
}
void nowPoint(long long val,int fa)
{
    tot++;
    size(tot) = cnt (tot) = 1;
    fa(tot)=fa;
    val(tot) = val;
}
void insert(long long val,int q)
{
    if( root[q] == 0 ){
        nowPoint(val,0);
        root[q] = tot;
        return;
    }
    int now = root[q];
    while( 1 ){
        size(now)++;
        if( val == val(now) )
        {
            cnt(now)++;
            splay(now,root[q],q);
            return;
        }
        int nxt = val > val(now) , son = t[now].ch[nxt];
        if( !son )
        {
            nowPoint(val,now);
            t[now].ch[nxt] = tot;
            splay(tot,root[q],q);
            return;
        }
        now = son ;
    }
}
int find(long long val,int q)
{
    int now = root[q];
    while( 1 ){
        if( !now )return 0;
        if( val == val(now) )
        {
            splay(now,root[q],q);
            return now ;
        }
        int nxt = val > val(now) , son = t[now].ch[nxt];
        now = son;
    }
}
void delet(long long val,int q)
{
    int now=find(val,q);
    if(!now)return;
    if( cnt(now) > 1 ){
        cnt(now)--; size(now)--;
        return;
    }
    if( ( !ls(now) && !rs(now) ) )
    {
        root[q] = 0;
        return;
    }else if( !ls(now) )
    {
        root[q] = rs(root[q]);
        fa(root[q]) = 0;
        return;
    }else if( !rs(now) )
    {
        root[q] = ls(root[q]);
        fa(root[q]) = 0;
        return;
    }else{
        int pos = ls(now);
        while(rs(pos)){
            pos = rs(pos);
        }
        splay(pos,ls(now),q);
        connect(rs(now),pos,1);
        connect(pos,0,1);
        root[q] = pos;
        update(pos);
    }
}
int rak(long long val,int q)
{
    insert(val,q);
    long long now = find(val,q);
    int k = size(ls(now)) + 1;
    delet(val,q);
    return k;
}
long long arak(int k,int q)
{
    int now = root[q];
    while( 1 )
    {
        int used = size(now) - size(rs(now));
        if( k > size(ls(now)) && k <= used ){
            break;
        }
        if( k<used ){
            now=ls(now);
        }else{
            now=rs(now);
            k-=used;
        }
    }
    splay(now,root[q],q);
    return val(now);
}
long long lower(long long val,int q)
{
    long long ans=-2147483647;
    int now = root[q];
    while( now )
    {
        if( val(now) < val && val(now) > ans ){
            ans = val(now);
        }
        if( val > val(now) ) now = rs(now);
        else now = ls(now);
    }
    return ans;
}
long long upper(long long val,int q)
{
    long long ans=2147483647;
    int now = root[q];
    while( now )
    {
        if( val(now) > val && val(now) < ans ){
            ans = val(now);
        }
        if( val < val(now) ) now = ls(now);
        else now = rs(now);
    }
    return ans;
}
void build(int l,int r,int p){
    tree[p].l = l;
    tree[p].r = r;
    if(l == r)
    {
        insert(a[l],p);
        tree[p].w=a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,(p<<1));
    build(mid+1,r,(p<<1|1));
    for(int i=l;i<=r;i++)
    {
        insert(a[i],p);
    }
}
int queryRank(int l,int r,int p,long long x)
{
    if(l<=tree[p].l&&r>=tree[p].r)
    {
     //   cout<<p<<" "<<tree[p].l<<" "<<tree[p].r<<" "<<rak(x,p)-1<<endl;
        return rak(x,p)-1;
    }
    int mid = (tree[p].l+tree[p].r) >> 1;
    int s=0;
    if(l <= mid)s += queryRank(l,r,(p<<1),x);
    if(r>mid) s+= queryRank(l,r,(p<<1|1),x);
    return s;
}
long long change(int pos,int p,long long k)
{
    if(tree[p].l == tree[p].r)
    {
        delet(tree[p].w,p);
        insert(k,p);
        return tree[p].w;
    }
    
    int mid = (tree[p].l+tree[p].r) >> 1;
    long long x;
    if(pos <= mid) 
    {
        x = change(pos,(p<<1),k);
    }
    if(pos>mid) 
    {
        x = change(pos,(p<<1|1),k);
    }
    delet(x,p);
    insert(k,p);
}
long long queryLower(int l,int r,int p,long long x)
{
    if(l<=tree[p].l&&r>=tree[p].r)
    {
        a[tree[p].l]=x;
        return lower(x,p);
    }
    int mid = (tree[p].l+tree[p].r) >> 1;
    long long ans = -0x7fffffff ;
    if(l <= mid)ans = max(queryLower(l,r,(p<<1),x),ans);
    if(r>mid) ans = max(queryLower(l,r,(p<<1|1),x),ans);
    return ans;
}
long long queryUpper(int l,int r,int p,long long x)
{
    if(l<=tree[p].l&&r>=tree[p].r)
    {
        return upper(x,p);
    }
    int mid = (tree[p].l+tree[p].r) >> 1;
    long long ans = 0x7fffffff ;
    if(l <= mid)ans = min(queryUpper(l,r,(p<<1),x),ans);
    if(r>mid) ans = min(queryUpper(l,r,(p<<1|1),x),ans);
    return ans;
}
long long query(int L,int R,long long k) {
    int ans = 0;
    int l=1,r=100000000;
    while(l<=r)
    {
        long long mid=(l+r)>>1;
        if(queryRank(L,R,1,mid)+1<=k)l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}
int main(){

    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,n,1);
    while ( T --> 0 )
    {
        int opt,l,r;long long k;
        cin>>opt;
        switch (opt)
        {
            case 1:
                cin>>l>>r>>k;
                cout<<queryRank(l,r,1,k)+1<<endl;   
                break;
            case 2:
                cin>>l>>r>>k;
                cout<<query(l,r,k)<<endl;
                break;
            case 3:
                cin>>l>>k;
                change(l,1,k);
                break;
            case 4:
                cin>>l>>r>>k;
                cout<< queryLower(l,r,1,k)<<endl;
                break;
            case 5:
                cin>>l>>r>>k;
                cout<<queryUpper(l,r,1,k)<<endl;
                break;
        }
    }
    return 0;
}