#include 
#include 
#include 
#include 
using namespace std;
#define reg register
inline int read() {int res = 0;char ch = getchar();bool fu = 0;while(!isdigit(ch)) fu |= (ch == '-'), ch = getchar();while(isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();return fu ? -res : res;
}
#define N 500005
int n, m, chushi[N], MAX;
namespace treap {int val[N * 50], siz[N * 50], ch[N * 50][2], pri[N * 50], tot;inline void update(int o) {siz[o] = siz[ch[o][0]] + siz[ch[o][1]] + 1;}inline int newnode(int v) {int jd = ++tot;siz[jd] = 1;val[jd] = v, pri[jd] = rand();return jd;}int Merge(int x, int y) {if (x * y == 0) return x + y;if (pri[x] < pri[y]) {ch[x][1] = Merge(ch[x][1], y);update(x);return x;} else {ch[y][0] = Merge(x, ch[y][0]);update(y);return y;}}void Split(int o, int k, int &x, int &y) {if (!o) {x = y = 0;return;}if (val[o] <= k) x = o, Split(ch[x][1], k, ch[x][1], y);else y = o, Split(ch[y][0], k, x, ch[y][0]);update(o);}inline void insert(int &root, int v) {int a = 0, b = 0;Split(root, v, a, b);root = Merge(Merge(a, newnode(v)), b);}inline void delet(int &root, int v){int a = 0, b = 0, c = 0;Split(root, v, a, b);Split(a, v - 1, a, c);c = Merge(ch[c][0], ch[c][1]);root = Merge(Merge(a, c), b);}inline int rnk(int &root, int v) {int a = 0, b = 0;Split(root, v - 1, a, b);int res = siz[a] - 1;//
        root = Merge(a, b);return res;}inline int kth(int o, int k) {while(1) {if (siz[ch[o][0]] >= k) o = ch[o][0];else if (siz[ch[o][0]] + 1 == k) return val[o];else k -= siz[ch[o][0]] + 1, o = ch[o][1];}}inline int findpre(int &root, int v) {int a = 0, b = 0;Split(root, v - 1, a, b);int res = kth(a, siz[a]);root = Merge(a, b);return res;}inline int findnxt(int &root, int v){int a = 0, b = 0;Split(root, v, a, b);int res = kth(b, 1);root = Merge(a, b);return res;}
}
int rt[N << 2];
#define ls o << 1
#define rs o << 1 | 1
void Build(int l, int r, int o)
{treap::insert(rt[o], 2147483647);treap::insert(rt[o], -2147483647);for (reg int i = l ; i <= r ; i ++) treap :: insert(rt[o], chushi[i]);if (l == r) return ;int mid = (l + r) >> 1;Build(l, mid, ls), Build(mid + 1, r, rs);
}
int queryrank(int l, int r, int o, int ql, int qr, int v)
{if (l >= ql and r <= qr) return treap::rnk(rt[o], v);int res = 0;int mid = (l + r) >> 1;if (ql <= mid) res += queryrank(l, mid, ls, ql, qr, v);if (qr > mid) res += queryrank(mid + 1, r, rs, ql, qr, v);return res;
}
inline int kth(int ql, int qr, int k)
{int l = 0, r = MAX;int res = 0;while(l <= r) {int mid = (l + r) >> 1;if (queryrank(1, n, 1, ql, qr, mid) + 1 <= k) res = mid, l = mid + 1;else r = mid - 1;}return res;
}
void change(int l, int r, int o, int pos, int v, int yuanshi)
{if (l == r) {treap::delet(rt[o], chushi[l]), chushi[l] = v, treap::insert(rt[o], v);return;}treap::delet(rt[o], yuanshi), treap::insert(rt[o], v);int mid = (l + r) >> 1;if (pos <= mid) change(l, mid, ls, pos, v, yuanshi);else change(mid + 1, r, rs, pos, v, yuanshi);
}
int ans;
void querypre(int l, int r, int o, int ql, int qr, int v)
{if (l >= ql and r <= qr) {ans = max(ans, treap::findpre(rt[o], v));return;}int mid = (l + r) >> 1;if (ql <= mid) querypre(l, mid, ls, ql, qr, v);if (qr > mid) querypre(mid + 1, r, rs, ql, qr, v);
}
void querynxt(int l, int r, int o, int ql, int qr, int v)
{if (l >= ql and r <= qr) {ans = min(ans, treap::findnxt(rt[o], v));return;}int mid = (l + r) >> 1;if (ql <= mid) querynxt(l, mid, ls, ql, qr, v);if (qr > mid) querynxt(mid + 1, r, rs, ql, qr, v);
}int main()
{n = read(), m = read();for (reg int i = 1 ; i <= n ; i ++) chushi[i] = read(), MAX = max(MAX, chushi[i]);Build(1, n, 1);while(m--){int opt = read(), l = 0, r = 0, p = 0, v = 0;if (opt == 1) l = read(), r = read(), v = read(), printf("%d\n", queryrank(1, n, 1, l, r, v) + 1);else if (opt == 2) l = read(), r = read(), v = read(), printf("%d\n", kth(l, r, v));else if (opt == 3) p = read(), v = read(), change(1, n, 1, p, v, chushi[p]);else if (opt == 4) l = read(), r = read(), v = read(), ans = -2147483647, querypre(1, n, 1, l, r, v), printf("%d\n", ans);else l = read(), r = read(), v = read(), ans = 2147483647, querynxt(1, n, 1, l, r, v), printf("%d\n", ans);}return 0;
}