#include <iostream>

using namespace std;

const int N = 2000010, INF = 1e9;

struct Splay_Node
{
	int s[2], p;
	int v, size;
	void init(int _v, int _p)
	{
		v = _v, p = _p;
		size = 1;
	}
}tr[N];

struct Segment_Tree_Node
{
	int l, r;
	int root;
}str[N];

int n, m, idx;
int w[N];

void pushup(int x)
{
	tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}

void rotate(int x)
{
	int y = tr[x].p, z = tr[y].p;
	int k = tr[y].s[1] == x;
	tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
	tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
	tr[x].s[k ^ 1] = y, tr[y].p = x;
	pushup(y), pushup(x);
}

void splay(int& root, int x, int k)
{
	while (tr[x].p != k)
	{
		int y = tr[x].p, z = tr[y].p;
		if (z != k)
			if ((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) rotate(x);
			else rotate(y);
		rotate(x);
	}
	if (!k) root = x;
}

void insert(int& root, int v)
{
	int u = root, p = 0;
	while (u) p = u, u = tr[u].s[v > tr[u].v]; 
	u = ++ idx;
	if (p) tr[p].s[v > tr[u].v] = u;
	tr[u].init(v, p);
	splay(root, u, 0);
}

void upper(int& root, int v)
{
	int u = root;
	while (tr[u].s[v > tr[u].v] && v != tr[u].v)
		u = tr[u].s[v > tr[u].v];
	splay(root, u, 0);
}

int get_rank(int& root, int v)
{
	upper(root, v);
	return tr[tr[root].s[0]].size;
}

int get_prev(int& root, int v)
{
	upper(root, v);
	if (tr[root].v < v) return root;
	int u = tr[root].s[0];
	while (tr[u].s[1]) u = tr[u].s[1];
	return u;
}

int get_next(int& root, int v)
{
	upper(root, v);
	if (tr[root].v > v) return root;
	int u = tr[root].s[1];
	while (tr[u].s[0]) u = tr[u].s[0];
	return u;
}

void update(int& root, int v, int nv)
{
	int l = get_prev(root, v), r = get_next(root, v);
	splay(root, l, 0), splay(root, r, l);
	tr[r].s[0] = 0;
	pushup(r), pushup(l);
	insert(root, nv);
}

void build(int u, int l, int r)
{
	str[u] = {l, r};
	for (int i = l; i <= r; i ++ )
		insert(str[u].root, w[i]);
	if (l == r) return;
	else
	{
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}

void modify(int u, int x, int c)
{
	update(str[u].root, x, c);
	if (str[u].l == str[u].r) return;
	else
	{
		int mid = str[u].l + str[u].r >> 1;
		if (x <= mid) modify(u << 1, x, c);
		else modify(u << 1 | 1, x, c);
	}
}

int query_rank(int u, int l, int r, int x)
{
	if (str[u].l >= l && str[u].r <= r)
		return get_rank(str[u].root, x);
	else
	{
		int mid = str[u].l + str[u].r >> 1, res = 0;
		if (l <= mid) res += query_rank(u << 1, l, r, x);
		if (r > mid) res += query_rank(u << 1 | 1, l, r, x);
		return res;
	}
}

int query_prev(int u, int l, int r, int x)
{
	if (str[u].l >= l && str[u].r <= r)
		return tr[get_prev(str[u].root, x)].v;
	else
	{
		int mid = str[u].l + str[u].r >> 1, res = -INF;
		if (l <= mid) res = max(res, query_prev(u << 1, l, r, x));
		if (r > mid) res = max(res, query_prev(u << 1 | 1, l, r, x));
		return res;
	}
}

int query_next(int u, int l, int r, int x)
{
	if (str[u].l >= l && str[u].r <= r)
		return tr[get_next(str[u].root, x)].v;
	else
	{
		int mid = str[u].l + str[u].r >> 1, res = INF;
		if (l <= mid) res = min(res, query_next(u << 1, l, r, x));
		if (r > mid) res = min(res, query_next(u << 1 | 1, l, r, x));
		return res;
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &w[i]);

	build(1, 1, n);

	int op, l, r, x;
	while (m -- )
	{
		scanf("%d%d%d", &op, &l, &r);
		if (op == 3) modify(1, l, r), w[l] = r;
		else
		{
			scanf("%d", &x);
			if (op == 1) printf("%d\n", query_rank(1, l, r, x));
			else if (op == 4) printf("%d\n", tr[query_prev(1, l, r, x)].v);
			else if (op == 5) printf("%d\n", tr[query_next(1, l, r, x)].v);
			else
			{
				int wl = -INF, wr = INF;
				while (wl < wr)
				{
					int mid = wl + wr + 1 >> 1;
					if (query_rank(1, l, r, mid) < x) wl = mid;
					else wr = mid - 1;
				}
				printf("%d\n", wr);
			}
		}
	}

	return 0;
}