#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e4 + 5, as = 1e7;
const ll inf = 2147483647;
ll n, m, op, x, y, k, a[maxn], si_ze, idx;
ll sz[as], l[as], r[as], val[as], key[as];
struct FHQ_Treap {
	ll root;
	inline ll New(ll v) {
		idx++;
		sz[idx] = 1;
		val[idx] = v;
		key[idx] = rand();
		return idx;
	}
	void Update(ll u) {
		sz[u] = sz[l[u]] + sz[r[u]] + 1;
		return;
	}
	void Split(ll u, ll v, ll &x, ll &y) {
		if (!u) {
			x = y = 0;
			return;
		}
		if (val[u] <= v) {
			x = u;
			Split(r[u], v, r[u], y);
		} else {
			y = u;
			Split(l[u], v, x, l[u]);
		}
		Update(u);
		return;
	}
	inline ll Merge(ll x, ll y) {
		if (!x || !y)
			return x | y;
		if (key[x] < key[y]) {
			r[x] = Merge(r[x], y);
			Update(x);
			return x;
		} else {
			l[y] = Merge(x, l[y]);
			Update(y);
			return y;
		}
	}
	void Insert(ll v) 	{
		ll x, y, z;
		z = New(v);
		Split(root, v, x, y);
		root = Merge(Merge(x, z), y);
		return;
	}
	void Delete(ll v) {
		ll x, y, z;
		Split(root, v, x, y);
		Split(x, v - 1, x, z);
		z = Merge(l[z], r[z]);
		root = Merge(Merge(x, z), y);
		return;
	}
	inline ll Rank(ll v) {
		ll x, y, ans;
		Split(root, v - 1, x, y);
		ans = sz[x] + 1;
		root = Merge(x, y);
		return ans;
	}
	inline ll K_th(ll u, ll k) 	{
		if (!u)
			return 1;
		if (sz[l[u]] + 1 == k)
			return val[u];
		if (k <= sz[l[u]])
			return K_th(l[u], k);
		return K_th(r[u], k - sz[l[u]] - 1);
	}
	inline ll Pre(ll v) 	{
		ll x, y, ans;
		if (K_th(root, 1) >= v)
			return -inf;
		Split(root, v - 1, x, y);
		ans = K_th(x, sz[x]);
		root = Merge(x, y);
		return ans;
	}
	inline ll Suc(ll v) 	{
		ll x, y, ans;
		if (K_th(root, sz[root]) <= v)
			return inf;
		Split(root, v, x, y);
		ans = K_th(y, 1);
		root = Merge(x, y);
		return ans;
	}
	void Build(ll l, ll r) {
		for (int i = l; i <= r; ++i)
			Insert(a[i]);
		return;
	}
};
struct SegTree {
	FHQ_Treap t[maxn << 2];
	void build(ll l, ll r, ll i) {
		t[i].Build(l, r);
		if (l == r)
			return;
		ll mid = (l + r) >> 1;
		build(l, mid, i << 1);
		build(mid + 1, r, i << 1 | 1);
		return;
	}
	void update(ll l, ll r, ll i, ll w, ll k) {
		t[i].Delete(a[w]);
		t[i].Insert(k);
		if (l == r && l == w) {
			a[w] = k;
			return;
		}
		ll mid = (l + r) >> 1;
		if (w <= mid)
			update(l, mid, i << 1, w, k);
		else
			update(mid + 1, r, i << 1 | 1, w, k);
		return;
	}
	ll rank(ll l, ll r, ll i, ll a, ll b, ll k) {
		if (a <= l && r <= b)
			return t[i].Rank(k) - 1;
		ll mid = (l + r) >> 1, ans = 0;
		if (a <= mid)
			ans += rank(l, mid, i << 1, a, b, k);
		if (mid < b)
			ans += rank(mid + 1, r, i << 1 | 1, a, b, k);
		return ans;
	}
	inline ll k_th(ll l, ll r, ll k) {
		ll x = 0, y = 1e9, ans = - 1;
		while (x <= y) {
			ll mid = (x + y) >> 1;
			if (rank(1, n, 1, l, r, mid) < k)
			{
				ans = mid;
				x = mid + 1;
			}
			else
				y = mid - 1;
		}
		return ans;
	}
	ll pre(ll l, ll r, ll i, ll a, ll b, ll k) {
		if (r < a || l > b)
			return -inf;
		if (a <= l && r <= b)
			return t[i].Pre(k);
		ll mid = (l + r) >> 1;
		return max(pre(l, mid, i << 1, a, b, k), pre(mid + 1, r, i << 1 | 1, a, b, k));
	}
	ll suc(ll l, ll r, ll i, ll a, ll b, ll k) {
		if (r < a || l > b)
			return inf;
		if (a <= l && r <= b)
			return t[i].Suc(k);	
		ll mid = (l + r) >> 1;
		return min(suc(l, mid, i << 1, a, b, k), suc(mid + 1, r, i << 1 | 1, a, b, k));
	}
} tree;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
        y=(y<<3)+(y<<1);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}
int main() {
	n = read();
	m = read();
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	tree.build(1, n, 1);
	while  (m--) {
		op = read();
		switch (op) {
            case 1 : {
            	x = read();
            	y = read();
            	k = read();
                write(tree.rank(1, n, 1, x, y, k) + 1);
				putchar('\n');
                break;   
            }
            case 2 : {
            	x = read();
            	y = read();
            	k = read();
                write(tree.k_th(x, y, k)); 
				putchar('\n');  
                break;  
            }
            case 3 : {
            	x = read();
            	y = read();
                tree.update(1, n, 1, x, y);
                break;
            }
            case 4 : {
            	x = read();
            	y = read();
            	k = read();
                write(tree.pre(1, n, 1, x, y, k)); 
				putchar('\n');
                break;
            }
            case 5 : {
            	x = read();
            	y = read();
            	k = read();
                write(tree.suc(1, n, 1, x, y, k)); 
				putchar('\n');    
                break;
            }
        }
	}
	return 0;
}

link