#include <bits/stdc++.h>
#define mk make_pair
#define pb emplace_back

using namespace std;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (! isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

const int maxn = 4e6 + 10, inf = 2147483647;
int n, m, mx, mn = 1e8, a[maxn]; mt19937 rnd(time(0));

namespace fhq {
	int tot, rd[maxn], v[maxn], ls[maxn], rs[maxn], sz[maxn];
	inline int cr(int va) { rd[++ tot] = rnd(), v[tot] = va, sz[tot] = 1; return tot; }
	inline void up(int p) { sz[p] = sz[ls[p]] + sz[rs[p]] + 1; }
	int merg(int x, int y) {
		if (!x || !y) return x + y;
		if (rd[x] < rd[y]) return rs[x] = merg(rs[x], y), up(x), x;
		else return ls[y] = merg(x, ls[y]), up(y), y;
	}

	void spl(int p, int k, int &x, int &y) {
		if (!p) return x = y = 0, void();
		if (v[p] <= k) x = p, spl(rs[p], k, rs[x], y);
		else y = p, spl(ls[p], k, x, ls[y]); up(p);
	}

	inline void ins(int &rt, int va) { int x, y; spl(rt, va, x, y); rt = merg(merg(x, cr(va)), y); }
	inline void del(int &rt, int va) { int x, y, z; spl(rt, va - 1, x, y), spl(y, va, y, z);
		y = merg(ls[y], rs[y]), rt = merg(merg(x, y), z); }
	
	inline int rnk(int &rt, int va) { int x, y, res; spl(rt, va - 1, x, y), res = sz[x], rt = merg(x, y); return res; }
	inline int pre(int &rt, int va) {
		int x, y, p; spl(rt, va - 1, x, y);
		p = x; while (rs[p]) p = rs[p]; rt = merg(x, y);
		return p ? v[p] : -inf;
	}

	inline int nxt(int &rt, int va) {
		int x, y, p; spl(rt, va, x, y); p = y;
		while (ls[p]) p = ls[p]; rt = merg(x, y);
		return p ? v[p] : inf;
	}
};

using namespace fhq;

namespace seg_fhq {
	int rt[maxn];
	void bld(int p, int l, int r) {
		for (int i = l; i <= r; i ++) ins(rt[p], a[i]);
		if (l == r) return ; int mi = l + r >> 1;
		bld(p << 1, l, mi), bld(p << 1 | 1, mi + 1, r);
	}

	int qrk(int p, int l, int r, int x, int y, int va) {
		if (x <= l && r <= y) return rnk(rt[p], va);
		int res = 0, mi = l + r >> 1;
		if (x <= mi) res += qrk(p << 1, l, mi, x, y, va);
		if (mi < y) res += qrk(p << 1 | 1, mi + 1, r, x, y, va);
		return res;
	}

	inline int qva(int L, int R, int rk) {
		int l = mn, r = mx;
		while (l + 1 < r) {
			int mi = l + r >> 1;
			if (qrk(1, 1, n, L, R, mi) < rk) l = mi;
			else r = mi;
		}

		if (qrk(1, 1, n, L, R, r) < rk) return r;
		return l;
	}

	void mdf(int p, int l, int r, int x, int va) {
        del(rt[p], a[x]), ins(rt[p], va);
		if (l == r) return a[l] = va, void();
		
		int mi = l + r >> 1;
		if (x <= mi) mdf(p << 1, l, mi, x, va);
		else mdf(p << 1 | 1, mi + 1, r, x, va);
	}

	int qpre(int p, int l, int r, int x, int y, int va) {
		if (x <= l && r <= y) return pre(rt[p], va);
		int mi = l + r >> 1, res = -inf;
		if (x <= mi) res = max(res, qpre(p << 1, l, mi, x, y, va));
		if (mi < y) res = max(res, qpre(p << 1 | 1, mi + 1, r, x, y, va));
		return res;
	}

	int qnxt(int p, int l, int r, int x, int y, int va) {
		if (x <= l && r <= y) return nxt(rt[p], va);
		int mi = l + r >> 1, res = inf;
		if (x <= mi) res = min(res, qnxt(p << 1, l, mi, x, y, va));
		if (mi < y) res = min(res, qnxt(p << 1 | 1, mi + 1, r, x, y, va));
		return res;
	}
}

using namespace seg_fhq;

int main() {
	
	n = read(), m = read();
	for (int i = 1; i <= n; i ++) mx = max(mx, a[i] = read()), mn = min(mn, a[i]);

	bld(1, 1, n);
	for (int i = 1; i <= m; i ++) {
		int op = read(), l, r, x, va;
		if (op == 1) l = read(), r = read(), va = read(), printf("%d\n", qrk(1, 1, n, l, r, va) + 1);
		else if (op == 2) l = read(), r = read(), va = read(), printf("%d\n", qva(l, r, va));
		else if (op == 3) x = read(), mx = max(mx, va = read()), mn = min(mn, a[i]), mdf(1, 1, n, x, va);
		else if (op == 4) l = read(), r = read(), va = read(), printf("%d\n", qpre(1, 1, n, l, r, va));
		else l = read(), r = read(), va = read(), printf("%d\n", qnxt(1, 1, n, l, r, va));
	}

	return 0;
}