// Problem: P6242 【模板】线段树 3
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6242
// Memory Limit: 500 MB
// Time Limit: 3500 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cstdio>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int a[500005], d[2000005], b1[2000005], b2[2000005], b3[2000005], b4[2000005],
    maxa[2000005], maxb[2000005], cnt[2000005], se[2000005];
void change(int l, int r, int p, int k1, int k2, int k3, int k4) {
    d[p] += k1 * cnt[p] + k2 * (r - l + 1 - cnt[p]);
    maxb[p] = max(maxb[p], maxa[p] + k3);
    maxa[p] += k1;
    if (se[p] != -inf)
        se[p] += k2;
    b3[p] = max(b3[p], b1[p] + k3);
    b4[p] = max(b4[p], b2[p] + k4);
    b1[p] += k1;
    b2[p] += k2;
}
void pushdown(int l, int r, int p) {
    int mid = (l + r) / 2;
    int maxn = max(maxa[p * 2], maxa[p * 2 + 1]);
    if (maxa[p * 2] == maxn) {
        change(l, mid, p * 2, b1[p], b2[p], b3[p], b4[p]);
    } else {
        change(l, mid, p * 2, b2[p], b2[p], b4[p], b4[p]);
    }
    if (maxa[p * 2 + 1] == maxn) {
        change(mid + 1, r, p * 2 + 1, b1[p], b2[p], b3[p], b4[p]);
    } else {
        change(mid + 1, r, p * 2 + 1, b2[p], b2[p], b4[p], b4[p]);
    }
    b1[p] = b2[p] = b3[p] = b4[p] = 0;
}
void pushup(int l, int r, int p) {
    d[p] = d[p * 2] + d[p * 2 + 1];
    maxa[p] = max(maxa[p * 2], maxa[p * 2 + 1]);
    maxb[p] = max(maxb[p * 2], maxb[p * 2 + 1]);
    if (maxa[p * 2] == maxa[p * 2 + 1]) {
        se[p] = max(se[p * 2], se[p * 2 + 1]);
        cnt[p] = cnt[p * 2] + cnt[p * 2 + 1];
    } else if (maxa[p * 2] > maxa[p * 2 + 1]) {
        se[p] = max(se[p * 2], maxa[p * 2 + 1]);
        cnt[p] = cnt[p * 2];
    } else {
        se[p] = max(maxa[p * 2], se[p * 2 + 1]);
        cnt[p] = cnt[p * 2 + 1];
    }
}
void build(int l, int r, int p) {
    if (l == r) {
        d[p] = maxa[p] = maxb[p] = a[l];
        cnt[p] = 1;
        se[p] = -inf;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, p * 2);
    build(mid + 1, r, p * 2 + 1);
    pushup(l, r, p);
}
void add(int l, int r, int p, int x, int y, int k) {
    if (x <= l && r <= y) {
        d[p] += k * (r - l + 1);
        maxa[p] += k;
        maxb[p] = max(maxb[p], maxa[p]);
        if (se[p] != -inf)
            se[p] += k;
        b1[p] += k;
        b2[p] += k;
        b3[p] = max(b3[p], b1[p]);
        b4[p] = max(b4[p], b2[p]);
        return;
    }
    pushdown(l, r, p);
    int mid = (l + r) / 2;
    if (x <= mid)
        add(l, mid, p * 2, x, y, k);
    if (mid < y)
        add(mid + 1, r, p * 2 + 1, x, y, k);
    pushup(l, r, p);
}
void update(int l, int r, int p, int x, int y, int k) {
    if (x <= l && r <= y && se[p] < k) {
        int v = maxa[p] - k;
        d[p] -= cnt[p] * v;
        maxa[p] = k;
        b1[p] -= k;
        return;
    }
    pushdown(l, r, p);
    int mid = (l + r) / 2;
    if (x <= mid && k < maxa[p * 2])
        update(l, mid, p * 2, x, y, k);
    if (mid < y && k < maxa[p * 2 + 1])
        update(mid + 1, r, p * 2 + 1, x, y, k);
    pushup(l, r, p);
}
int getsum(int l, int r, int p, int x, int y) {
    if (x <= l && r <= y) {
        return d[p];
    }
    int sum = 0;
    int mid = (l + r) / 2;
    if (x <= mid)
        sum += getsum(l, mid, p * 2, x, y);
    if (mid < y)
        sum += getsum(mid + 1, r, p * 2 + 1, x, y);
    return sum;
}
int getmaxa(int l, int r, int p, int x, int y) {
    if (x <= l && r <= y) {
        return maxa[p];
    }
    int mx = -inf;
    int mid = (l + r) / 2;
    if (x <= mid)
        mx = max(mx, getmaxa(l, mid, p * 2, x, y));
    if (mid < y)
        mx = max(mx, getmaxa(mid + 1, r, p * 2 + 1, x, y));
    return mx;
}
int getmaxb(int l, int r, int p, int x, int y) {
    if (x <= l && r <= y) {
        return maxb[p];
    }
    int mx = -inf;
    int mid = (l + r) / 2;
    if (x <= mid)
        mx = max(mx, getmaxa(l, mid, p * 2, x, y));
    if (mid < y)
        mx = max(mx, getmaxa(mid + 1, r, p * 2 + 1, x, y));
    return mx;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    build(1, n, 1);
    for (int i = 1; i <= m; i++) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            add(1, n, 1, l, r, k);
        } else if (op == 2) {
            int l, r, v;
            scanf("%d%d%d", &l, &r, &v);
            update(1, n, 1, l, r, v);
        } else if (op == 3) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", getsum(1, n, 1, l, r));
        } else if (op == 4) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", getmaxa(1, n, 1, l, r));
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", getmaxb(1, n, 1, l, r));
        }
    }
    return 0;
}