#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

template <typename T, const int __size> class rotational_treap {
	public:
		rotational_treap() {}
		~rotational_treap() {}
		int root, cur, temp, left_child[__size + 5], right_child[__size + 5], cnt[__size + 5], rank[__size + 5], _size[__size + 5];
		T value[__size + 5];
		inline void pushup(int pos) {
			_size[pos] = _size[left_child[pos]] + _size[right_child[pos]] + cnt[pos];
		}
		inline void left_rotate(int &pos) {
			int temp = right_child[pos];
			right_child[pos] = left_child[temp];
			left_child[temp] = pos;
			_size[temp] = _size[pos];
			pushup(pos);
			pos = temp;
		}
		inline void right_rotate(int &pos) {
			int temp = left_child[pos];
			left_child[pos] = right_child[temp];
			right_child[temp] = pos;
			_size[temp] = _size[pos];
			pushup(pos);
			pos = temp;
		}
		void _insert(int &pos, T v) {
			if (!pos) {
				++cur;
				pos = cur;
				cnt[pos] = 1;
				rank[pos] = rand();
				_size[pos] = 1;
				value[pos] = v;
				return;
			}
			++_size[pos];
			if (value[pos] < v) {
				_insert(right_child[pos], v);
				if (rank[right_child[pos]] < rank[pos])
					left_rotate(pos);
				return;
			}
			if (value[pos] > v) {
				_insert(left_child[pos], v);
				if (rank[left_child[pos]] < rank[pos])
					right_rotate(pos);
				return;
			}
			++cnt[pos];
		}
		void _remove(int &pos, T v) {
			if (!pos)
				return;
			if (value[pos] == v) {
				if (cnt[pos] > 1) {
					--cnt[pos];
					--_size[pos];
					return;
				}
				if (!left_child[pos] || !right_child[pos]) {
					pos = left_child[pos] + right_child[pos];
					return;
				}
				if (rank[left_child[pos]] < rank[right_child[pos]])
					right_rotate(pos);
				else
					left_rotate(pos);
				_remove(pos, v);
				return;
			}
			if (value[pos] < v)
				_remove(right_child[pos], v);
			else
				_remove(left_child[pos], v);
			--_size[pos];
		}
		int _rank(int pos, T v) {
			if (!pos)
				return 0;
			if (value[pos] == v)
				return _size[left_child[pos]] + 1;
			if (value[pos] < v)
				return _size[left_child[pos]] + cnt[pos] + _rank(right_child[pos], v);
			return _rank(left_child[pos], v);
		}
		T _value(int pos, int rank) {
			if (!pos)
				return 0;
			if (rank <= _size[left_child[pos]])
				return _value(left_child[pos], rank);
			if (rank > _size[left_child[pos]] + cnt[pos])
				return _value(right_child[pos], rank - _size[left_child[pos]] - cnt[pos]);
			return value[pos];
		}
		void _prev(int pos, T v) {
			if (!pos)
				return;
			if (value[pos] < v) {
				temp = pos;
				_prev(right_child[pos], v);
				return;
			}
			_prev(left_child[pos], v);
		}
		void _next(int pos, T v) {
			if (!pos)
				return;
			if (value[pos] > v) {
				temp = pos;
				_next(left_child[pos], v);
				return;
			}
			_next(right_child[pos], v);
		}
		inline T prev(int pos, T v) {
			_prev(pos, v);
			return temp;
		}
		inline T next(int pos, T v) {
			_next(pos, v);
			return temp;
		}
};

template <typename T, const int _size> class rotational_treap_in_segment_tree {
	private:
		struct node {
			int l, r, root;
		};
	protected:
		int n;
		T data[_size + 5];
		rotational_treap<T, _size> treap;
		node tree[_size << 3];
		void build(int pos, int l, int r) {
			tree[pos] = {l, r, tree[pos].root};
			for (register int i = l; i <= r; ++i)
				treap._insert(tree[pos].root, data[i]);
			if (l == r)
				return;
			int mid = l + r >> 1;
			build(pos << 1, l, mid);
			build(pos << 1 | 1, mid + 1, r);
		}
		void modify(int pos, int cur, T v) {
			treap._remove(tree[pos].root, data[cur]);
			treap._insert(tree[pos].root, v);
			if (tree[pos].l == tree[pos].r)
				return;
			int mid = tree[pos].l + tree[pos].r >> 1;
			if (cur <= mid)
				modify(pos << 1, cur, v);
			else
				modify(pos << 1 | 1, cur, v);
		}
		int rank(int pos, int l, int r, T v) {
			if (tree[pos].l > r || tree[pos].r < l)
				return 0;
			if (tree[pos].l >= l && tree[pos].r <= r)
				return treap._rank(tree[pos].root, v);
			return rank(pos << 1, l, r, v) + rank(pos << 1 | 1, l, r, v);
		}
		T prev(int pos, int l, int r, T v) {
			if (tree[pos].l > r || tree[pos].r < l)
				return -2147483647;
			if (tree[pos].l >= l && tree[pos].r <= r)
				return treap.prev(tree[pos].root, v);
			return max(prev(pos << 1, l, r, v), prev(pos << 1 | 1, l, r, v));
		}
		T next(int pos, int l, int r, T v) {
			if (tree[pos].l > r || tree[pos].r < l)
				return 2147483647;
			if (tree[pos].l >= l && tree[pos].r <= r)
				return treap.next(tree[pos].root, v);
			return min(next(pos << 1, l, r, v), next(pos << 1 | 1, l, r, v));
		}
	public:
		rotational_treap_in_segment_tree() {}
		~rotational_treap_in_segment_tree() {}
		inline void build(int N, T a[]) {
			n = N;
			for (register int i = 1; i <= n; ++i)
				data[i] = a[i];
			build(1, 1, n);
		}
		inline void modify(int pos, T v) {
			modify(1, pos, v);
			data[pos] = v;
		}
		inline int rank(int l, int r, T v) {
			return rank(1, l, r, v) + 1;
		}
		inline T value(int l, int r, int k) {
			T L = 0, R = 1e8, mid;
			while (L < R) {
				mid = L + R + 1 >> 1;
				if (rank(1, l, r, mid) < k)
					L = mid;
				else
					R = mid - 1;
			}
			return L;
		}
		inline T prev(int l, int r, T v) {
			return prev(1, l, r, v);
		}
		inline T next(int l, int r, T v) {
			return next(1, l, r, v);
		}
};

int n, m, opt, l, r, k, a[50005];
rotational_treap_in_segment_tree<int, 50000> tree;

int main() {
	srand(time(0));
	scanf("%d%d", &n, &m);
	for (register int i = 1; i <= n; ++i)
		scanf("%d", a + i);
	tree.build(n, a);
	while (m--) {
		scanf("%d%d%d", &opt, &l, &r);
		switch (opt) {
			case 1:
				scanf("%d", &k);
				printf("%d\n", tree.rank(l, r, k));
				break;
			case 2:
				scanf("%d", &k);
				printf("%d\n", tree.value(l, r, k));
				break;
			case 3:
				tree.modify(l, r);
				break;
			case 4:
				scanf("%d", &k);
				printf("%d\n", tree.prev(l, r, k));
				break;
			default:
				scanf("%d", &k);
				printf("%d\n", tree.next(l, r, k));
		}
	}
	return 0;
}