#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e5 + 10;
int cnt;
int n,m,a[M];
namespace Treap {
	struct Node
	{
	    int ls, rs;
	    int key = -0x3f3f3f3f, pri;
	    int size;
	} t[M*4];
	void newnode(int x)
	{
	    cnt++;
	    t[cnt].size = 1;
	    t[cnt].ls = t[cnt].rs = 0;
	    t[cnt].key = x;
	    t[cnt].pri = rand();
	}
	void update(int u)
	{
	    t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
	}
	void rotate(int &o, int d)
	{ // d=0左旋，d=1右旋
	    int k;
	    if (d == 1)
	    {
	        k = t[o].rs;
	        t[o].rs = t[k].ls;
	        t[k].ls = o;
	    }
	    else
	    {
	        k = t[o].ls;
	        t[o].ls = t[k].rs;
	        t[k].rs = o;
	    }
	    t[k].size = t[o].size;
	    update(o);
	    o = k;
	}
	void Insert(int &u, int x) //插入 
	{
	    if (u == 0)
	    {
	        newnode(x);
	        u = cnt;
	        return;
	    } 
	    t[u].size++;
	    if (x >= t[u].key)
	    {
	        Insert(t[u].rs, x);
	    }
	    else
	        Insert(t[u].ls, x);
	    if (t[u].ls != 0 && t[u].pri > t[t[u].ls].pri)
	        rotate(u, 0);
	    if (t[u].rs != 0 && t[u].pri > t[t[u].rs].pri)
	        rotate(u, 1);
	    update(u);
	}
	void Del(int &u, int x) //删除 
	{
	    t[u].size--;
	    if (x == t[u].key)
	    { 
	        if (t[u].ls == 0 && t[u].rs == 0)
	        {
	            u = 0;
	            return;
	        }
	        if (t[u].ls == 0 || t[u].rs == 0)
	        {
	            u = t[u].ls + t[u].rs;
	            return;
	        }
	        if (t[t[u].ls].pri < t[t[u].rs].pri)
	        {
	            rotate(u, 0);
	            Del(t[u].rs, x);
	            return;
	        }
	        else
	        {
	            rotate(u, 1), Del(t[u].ls, x);
	            return;
	        }
	    }
	    if (t[u].key >= x)
	        Del(t[u].ls, x);
	    else
	        Del(t[u].rs, x);
	    update(u);
	}
	int Rank(int u, int x) //求排名 
	{
	    if (u == 0)
	        return 0;
	    if (x > t[u].key)
	        return t[t[u].ls].size + 1 + Rank(t[u].rs, x); 
	    return Rank(t[u].ls, x);
	}
	int kth(int u, int k) //查排名为 k 的数 
	{
	    if (k == t[t[u].ls].size + 1)
	        return t[u].key;
	    if (k > t[t[u].ls].size + 1)
	        return kth(t[u].rs, k - t[t[u].ls].size - 1);
	    if (k <= t[t[u].ls].size)
	        return kth(t[u].ls, k);
	}
	int precusor(int u, int x) //前驱 
	{
	    if (u == 0)
	        return 0;
	    if (t[u].key >= x)
	        return precusor(t[u].ls, x);
	    int tmp = precusor(t[u].rs, x);
	    if (tmp == 0)
	        return t[u].key;
	    return tmp; 
	}
	int succesor(int u, int x) //后继 
	{
	    if (u == 0)
	        return 0;
	    if (t[u].key <= x)
	        return succesor(t[u].rs, x);
	    int tmp = succesor(t[u].ls, x); 
	    if (tmp == 0)
	        return t[u].key;
	    return tmp;
	}

}
using namespace Treap;
namespace Seg {
	struct node{
		int l,r,root;
	};
	node tree[M*8];
	void build(int p,int l,int r) {
		tree[p].l=l,tree[p].r=r;
		for(int i=l;i<=r;i++) {
			Insert(tree[p].root,a[i]);
		}
		if(l!=r) {
			int mid=(l+r)/2;
			build(p*2,l,mid);
			build(p*2+1,mid+1,r);
		}
	}
	void change(int p,int x,int y) {
		Del(tree[p].root,a[x]);
		Insert(tree[p].root,y);
		if(tree[p].l==tree[p].r) {
			return;
		}
		int mid=(tree[p].l+tree[p].r)/2;
		if(x>mid) change(p*2+1,x,y);
		else {
			change(p*2,x,y);
		}
	}
	int queryrk(int p,int l,int r,int x) {
		if(tree[p].l>r||tree[p].r<l) {
			return 0;
		}
		if(tree[p].l>=l&&tree[p].r<=r) {
			return Rank(tree[p].root,x);
		}
		else {
			return queryrk(p*2,l,r,x)+queryrk(p*2+1,l,r,x);
		}
	}
	int querynum(int x,int y,int k) {
		int l=0,r=1e8;
		while(l<=r) {
			int mid=(l+r)/2;
			if(queryrk(1,x,y,mid)<=k) {
				l=mid+1;
			}
			else r=mid-1;
		}
		return l; 
	}
	int getpre(int p,int l,int r,int k) {
		if(tree[p].l>r||tree[p].r<l) {
			return -2147483647;
		}
		if(l<=tree[p].l&&r>=tree[p].r) {
			return precusor(tree[p].root,k);
		}
		return max(getpre(p*2,l,r,k),getpre(p*2+1,l,r,k));
	}
	int getsuc(int p,int l,int r,int k) {
		if(tree[p].l>r||tree[p].r<l) {
			return 2147483647;
		}
		if(l<=tree[p].l&&r>=tree[p].r) {
			return succesor(tree[p].root,k);
		}
		return min(getsuc(p*2,l,r,k),getsuc(p*2+1,l,r,k));
	}
}
using namespace Seg;
signed main()
{
//    cin.tie(0), cout.tie(0);
//    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--) {
    	int op,x,y,z;
    	cin>>op;
		if(op==3) {
			cin>>x>>y;
			change(1,x,y);
			a[x]=y;
			continue;
		}
    	if(op==1) {
    		cin>>x>>y>>z;
    		cout<<queryrk(1,x,y,z);
		}
		if(op==2){
			cin>>x>>y>>z;
			cout<<querynum(x,y,z);
		}
		
		if(op==4) {
			cin>>x>>y>>z;
			cout<<getpre(1,x,y,z);
		}
		if(op==5) {
			cin>>x>>y>>z;
			cout<<getsuc(1,x,y,z);
		}
		cout<<"\n";
	}
	return 0;
}