#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define i128 __int128
#define mem(x, y) memset(x, y, sizeof x)
#define lid (id << 1)
#define rid (id << 1 | 1)
#define fin(x) freopen(#x".in", "r", stdin)
#define fout(x) freopen(#x".out", "w", stdout)
const int N = 5e4+5;
namespace io {
	#define fastio ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    #ifdef ONLINE_JUDGE
    	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    #else
    	#define gc() getchar()
    #endif
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
    inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    template <class I> inline void read(I &x){ for (f = 1, c = gc(); c < 48 || c > 57; c = gc()) if (c == '-') f = -1; for (x = 0; c <= 57 && c >= 48; c = gc()) x = (x << 3) + (x << 1) + (c & 15); x *= f; }
    inline void read(char &ch) { ch = gc(); while (ch < 'A' || ch > 'z' || (ch > 'Z' && ch < 'a')) ch = gc(); }
    template <typename T, typename TT> inline void read(pair<T, TT> &a){read(a.first);read(a.second);}
    template <typename T, typename... Args> inline void read(T &num, Args &...args) { read(num), read(args...); }
    template <class I> inline void wr(I x) { if (!x) putc(48); if (x < 0) putc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + 48,  x /= 10; while (qr) putc (qu[qr --]); }
    template <> inline void wr(char ch){ putc(ch); }
    template <typename T, typename TT> inline void wr(pair<T, TT> a, char _sep){wr(a.first);wr(_sep);wr(a.second);}
    inline void wr1(){ wr('\n'); }
    inline void wr2(){ ; }
    template <typename T, typename... Args> inline void wr1(T num, Args... args) {wr(num), wr(' '), wr1(args...) ;}
    template <typename T, typename... Args> inline void wr2(T num, Args... args) {wr(num), wr('\n'), wr2(args...) ;}
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::read;
using io::wr;
using io::wr1;
using io::wr2;
namespace segt_in_bit{
	const int minnum = 0, maxnum = 1e8;
	struct node{
		int lc, rc;
		int sum;
	}tr[N * 400];
	int cnt;
	int root[N];
	int q[2][N];
	void modify(int &k, int l, int r, int pos, int val){
		if (!k) k = ++cnt;
		tr[k].sum += val;
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (pos <= mid) modify(tr[k].lc, l, mid, pos, val);
		else modify(tr[k].rc, mid + 1, r, pos, val);
	}
	inline void pre_modify(int x, int v, int qwq, int n){
		for (int i = x;i <= n;i += i & -i) modify(root[i], minnum, maxnum, qwq, v);
	}
	int qrank(int l, int r, int k){
		if (l >= r) return 0;
		int mid = (l + r) >> 1;
		if (k <= mid){
			for (int i = 1;i <= q[1][0];++i) q[1][i] = tr[q[1][i]].lc;
			for (int i = 1;i <= q[0][0];++i) q[0][i] = tr[q[0][i]].lc;
			return qrank(l, mid, k);
		}
		else{
			int x = 0;
			for (int i = 1;i <= q[1][0];++i) x += tr[tr[q[1][i]].lc].sum, q[1][i] = tr[q[1][i]].rc;
			for (int i = 1;i <= q[0][0];++i) x -= tr[tr[q[0][i]].lc].sum, q[0][i] = tr[q[0][i]].rc;
			return x + qrank(mid + 1, r, k);
		}
	}
	inline int pre_qrank(int l, int r, int k){
		q[0][0] = q[1][0] = 0;
		for (int i = l - 1;i;i -= i & -i) q[0][++q[0][0]] = root[i];
		for (int i = r;i;i -= i & -i) q[1][++q[1][0]] = root[i];
		return qrank(minnum, maxnum, k) + 1;
	}
	int kth(int l, int r, int k){
		if (l >= r) return l;
		int x = 0;
		for (int i = 1;i <= q[1][0];++i) x += tr[tr[q[1][i]].lc].sum;
		for (int i = 1;i <= q[0][0];++i) x -= tr[tr[q[0][i]].lc].sum;
		if (x >= k){
			for (int i = 1;i <= q[1][0];++i) q[1][i] = tr[q[1][i]].lc;
			for (int i = 1;i <= q[0][0];++i) q[0][i] = tr[q[0][i]].lc;
			return kth(l, (l + r) >> 1, k);
		}
		else{
			for (int i = 1;i <= q[1][0];++i) q[1][i] = tr[q[1][i]].rc;
			for (int i = 1;i <= q[0][0];++i) q[0][i] = tr[q[0][i]].rc;
			return kth(((l + r) >> 1) + 1, r, k - x);
		}
	}
	inline int pre_kth(int l, int r, int k){
		q[0][0] = q[1][0] = 0;
		for (int i = l - 1;i;i -= i & -i) q[0][++q[0][0]] = root[i];
		for (int i = r;i;i -= i & -i) q[1][++q[1][0]] = root[i];
		return kth(minnum, maxnum, k);
	}
	inline int qpre(int l, int r, int k){
		int x = pre_qrank(l, r, k);
		if (!--x) return -INT_MAX;
		return pre_kth(l, r, x);
	}
	inline int qsuf(int l, int r, int k){
		int x = pre_qrank(l, r, k + 1);
		if (x > r - l + 1) return INT_MAX;
		return pre_kth(l, r, x);
	}
}
using segt_in_bit::pre_modify;
using segt_in_bit::pre_qrank;
using segt_in_bit::pre_kth;
using segt_in_bit::qpre;
using segt_in_bit::qsuf;
namespace tianyu{
	mt19937 rd(time(0));
	int n, m;
	int a1[N], b[N << 1], tot;
	struct que{
		int op, a, b, c;
	}q[N];
	void awa(){
		read(n, m);
		for (int i = 1;i <= n;i++){
			read(a1[i]);
		}
		for (int i = 1;i <= n;i++) pre_modify(i, 1, a1[i], n);
		for (int i = 1;i <= m;i++){
			int op, a, b, c;
			read(op, a, b);
			if (op != 3) read(c);
			if (op == 1){
				wr2(pre_qrank(a, b, c));
			}
			else if (op == 2){
				wr2(pre_kth(a, b, c));
			}
			else if (op == 3){
				pre_modify(a, -1, a1[a], n);
				a1[a] = b;
				pre_modify(a, 1, a1[a], n);
			}
			else if (op == 4){
				wr2(qpre(a, b, c));
			}
			else{
				wr2(qsuf(a, b, c));
			}
		}
	}
}
_Atomic_word main(){ 
	int T = 1;
	while (T-->0){
		tianyu::awa();
	}
	return EXIT_SUCCESS;
}