#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = (2e5 + 20);
const ll inf = (1ll << 31) - 1;
ll n, m, op, x, y, k, a[maxn >> 2], si_ze, idx;
ll sz[maxn], l[maxn], r[maxn], val[maxn], key[maxn];
struct FHQ_Treap {
	ll root;
	void dfs(ll u) {
		if (!u)
			return;
		dfs(l[u]);
		cout << val[u] << ' ';
		dfs(r[u]);
	}
	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;
	}
};
struct SegTree {
	FHQ_Treap t[maxn];
	void build(ll l, ll r, ll i) {
		for (int ii = l; ii <= r; ii++)
			t[i].Insert(a[ii]);
		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;
	}
	ll k_th(ll l, ll r, ll k) {
		ll x = 0, y = 1e9, ans = - 1;
		while (x <= y) {
//			cout << x << ' ' << y << '\n';
//			Sleep(100);
			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 (a <= l && r <= b)
			return t[i].Pre(k);
		ll mid = (l + r) >> 1, ans = -1e18;
		if (a <= mid)
			ans = max(ans, pre(l, mid, i << 1, a, b, k));
		if (mid < b)
			ans = max(ans, pre(mid + 1, r, i << 1 | 1, a, b, k));
		return ans;
	}
	ll suc(ll l, ll r, ll i, ll a, ll b, ll k) {
		
		if (a <= l && r <= b) {
	//		cout << l << ' ' << r << ' ' <<  t[i].Suc(k) << '\n';
			return t[i].Suc(k);
		}
			
		ll mid = (l + r) >> 1, ans = 1e18;
		if (a <= mid)
			ans = min(ans, suc(l, mid, i << 1, a, b, k));
		if (mid < b)
			ans = min(ans, suc(mid + 1, r, i << 1 | 1, a, b, k));
		return ans;
	}
} tree;
inline ll read(){
    ll x=0,tmp=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') tmp=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return tmp*x;
}

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() {
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		a[i] = read();
	tree.build(1, n, 1);
//	cout << tree.suc(1, n, 1, 2, 8, 5) << '\n';
	while  (m--) {
		op = read(), x = read(), y = read();
		if (op != 3)
			k = read();
		if (op == 1)
			cout << tree.rank(1, n, 1, x, y, k) + 1 << '\n';
		else if (op == 2)
			cout << tree.k_th(x, y, k) << '\n';
		else if (op == 3)
			tree.update(1, n, 1, x, y);
		else if (op == 4)
			cout << tree.pre(1, n, 1, x, y, k) << '\n';
		else if (op == 5)
			cout << tree.suc(1, n, 1, x, y, k) << '\n';
	}
	return 0;
}
/*
9 1
4 2 2 10 9 4 0 1 1
5 2 8 5


4 2 2 10 9 4 0 1 1
4 2 2 10 9		4 0 1 1
4 2 2		10 9		4 0		1 1
4 2		2 	10 9 	4 	0	1 	1
4	2



*/

输入都 MLE ，有快读，不知道什么问题。

link