//
// Created by GRH on 2020/10/7.
//

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1500010, INF = 1e9;

int n, m;
struct Node {
    int s[2];       // 子节点id
    int p;          // 父节点id
    int v;          // 节点数值
    int size;       // 子树大小

    void init(int _v, int _p) {
        v = _v, p = _p;
        size = 1;
    }
} nodes[N];        // splay树节点缓存

int L[N], R[N];     // 线段树节点区间的左右边界
int ROOT[N];        // splay的根节点
int global_idx;     // splay节点缓存的末尾存储位置
int data_buf[N];

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

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

// x节点旋转到k节点下面
void splay_move(int& root, int x, int k) {
    while (nodes[x].p != k) {
        int y = nodes[x].p, z = nodes[y].p;
        if (z != k) {
            if ((nodes[y].s[1] == x) != (nodes[z].s[1] == y)) {
                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 = nodes[u].s[v > nodes[u].v];
    }

    u = ++global_idx;
    if (p) {
        nodes[p].s[v > nodes[p].v] = u;
    }

    nodes[u].init(v, p);
    splay_move(root, u, 0);
}

// 比v小的节点数量
int get_k(int root, int v)
{
    int u = root, res = 0;
    while (u)
    {
        if (nodes[u].v < v) {
            res += nodes[nodes[u].s[0]].size + 1;
            u = nodes[u].s[1];
        }
        else {
            u = nodes[u].s[0];
        }
    }
    return res;
}

// 小于等于v的节点的数量
int get_k_lower_equal(int root, int v) {
    int u = root, res = 0;
    while (u)
    {
        if (nodes[u].v <= v) {
            res += nodes[nodes[u].s[0]].size + 1;
            u = nodes[u].s[1];
        }
        else {
            u = nodes[u].s[0];
        }
    }
    return res;
}

// 更新原值为x的节点数值为新值y
void update(int& root, int x, int y)
{
    int u = root;
    while (u) {
        if (nodes[u].v == x) {
            break;
        }

        if (nodes[u].v < x) {
            u = nodes[u].s[1];
        }
        else {
            u = nodes[u].s[0];
        }
    }

    splay_move(root, u, 0);
    int l = nodes[u].s[0], r = nodes[u].s[1];
    while (nodes[l].s[1]) {
        l = nodes[l].s[1];
    }

    while (nodes[r].s[0]) {
        r = nodes[r].s[0];
    }

    splay_move(root, l, 0), splay_move(root, r, l);
    nodes[r].s[0] = 0;
    pushup(r);
    pushup(l);
    insert(root, y);
}

// 递归构建线段树
void build(int u, int l, int r)
{
    L[u] = l, R[u] = r;

    // 哨兵
    insert(ROOT[u], -INF);
    insert(ROOT[u], INF);

    for (int i = l; i <= r; i ++ ) {
        insert(ROOT[u], data_buf[i]);
    }

    if (l == r) {
        return;
    }

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

// 区间[start, end]中小于x的节点数量
int query(int u, int start, int end, int x) {
    if (L[u] == start && R[u] == end) {
        return get_k(ROOT[u], x) - 1;   // 哨兵多减去1
    }

    int mid = (L[u] + R[u]) >> 1;
    if (end <= mid) {
        return query(u << 1, start, end, x);
    } else if (start >= mid+1) {
        return query(u<<1 | 1, start, end, x);
    } else {
        return query(u << 1, start, mid, x) + query(u<<1 | 1, mid+1, end, x);
    }
}

// 区间[start, end]中小于等于x的节点数量
int query_lower_equal(int u, int start, int end, int x) {
    if (L[u] == start && R[u] == end) {
        return get_k_lower_equal(ROOT[u], x) - 1;   // 哨兵多减去1
    }

    int mid = (L[u] + R[u]) >> 1;
    if (end <= mid) {
        return query_lower_equal(u << 1, start, end, x);
    } else if (start >= mid+1) {
        return query_lower_equal(u<<1 | 1, start, end, x);
    } else {
        return query_lower_equal(u << 1, start, mid, x) + query_lower_equal(u<<1 | 1, mid+1, end, x);
    }
}

// 更新p位置数据为x
void change(int u, int p, int x) {
    update(ROOT[u], data_buf[p], x);
    if (L[u] == R[u]) {
        return;
    }

    int mid = (L[u] + R[u]) >> 1;
    if (p <= mid) {
        change(u << 1, p, x);
    } else {
        change(u << 1 | 1, p, x);
    }
}

// 获取splay前驱节点， 比v小的最大的节点
int get_pre(int root, int v) {
    int u = root, res = -INF;
    while (u) {
        if (nodes[u].v < v) {
            res = max(res, nodes[u].v);
            u = nodes[u].s[1];
        } else {
            u = nodes[u].s[0];
        }
    }

    return res;
}

// 获取splay后继节点，比v大的最小的节点
int get_suc(int root, int v) {
    int u = root, res = INF;
    while (u) {
        if (nodes[u].v > v) {
            res = min(res, nodes[u].v);
            u = nodes[u].s[0];
        }
        else {
            u = nodes[u].s[1];
        }
    }
    return res;
}

// 节点u查找区间[start, end]中小于x的最大值
int query_pre(int u, int start, int end, int x) {
    if (L[u] == start && R[u] == end) {
        return get_pre(ROOT[u], x);
    }

    int mid = (L[u] + R[u]) >> 1, res = -INF;
    if (end <= mid) {
        return query_pre(u<<1, start, end, x);
    } else if (start >= mid+1) {
        return query_pre(u<<1 | 1, start, end, x);
    } else {
        return max(query_pre(u<<1, start, mid, x), query_pre(u<<1 | 1, mid+1, end, x));
    }
}

// 节点u查找区间[start, end]中大于x的最小值
int query_suc(int u, int start, int end, int x)
{
    if (L[u] == start && R[u] == end) {
        return get_suc(ROOT[u], x);
    }

    int mid = (L[u] + R[u]) >> 1;
    if (end <= mid) {
        return query_suc(u<<1, start, end, x);
    } else if (start >= mid + 1) {
        return query_suc(u<<1 | 1, start, end, x);
    } else {
        return min(query_suc(u<<1, start, mid, x), query_suc(u<<1 | 1, mid+1, end, x));
    }
}

int main()
{
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

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

    while (m -- )
    {
        int op, a, b, x;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d%d", &a, &b, &x);
            printf("%d\n", query(1, a, b, x) + 1);
        }
        else if (op == 2)
        {
            scanf("%d%d%d", &a, &b, &x);
            int l = 0, r = 1e8;
            int ans = 0;
            while (l <= r) {
                int mid = (l+r) >> 1;
                if (query_lower_equal(1, a, b, mid) >= x) {
                    r = mid - 1;
                    ans = mid;
                } else {
                    l = mid + 1;
                }
            }
            printf("%d\n", ans);
        }
        else if (op == 3)
        {
            scanf("%d%d", &a, &x);
            change(1, a, x);
            data_buf[a] = x;
        }
        else if (op == 4)
        {
            scanf("%d%d%d", &a, &b, &x);
            printf("%d\n", query_pre(1, a, b, x));
        }
        else
        {
            scanf("%d%d%d", &a, &b, &x);
            printf("%d\n", query_suc(1, a, b, x));
        }
    }

    return 0;
}