#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace FASTIO {
    inline int read() {
        int res = 0, f = 1;
        char ch = getchar();
        while (!isdigit (ch)) f = ch == '-' ? -1 : 1, ch = getchar();
        while (isdigit (ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
        return res * f;
    }
    inline void write (int x) {
        int st[33], top = 0;
        if (x < 0) x = -x, putchar ('-');
        do { st[top ++] = x % 10, x /= 10; } while (x);
        while (top) putchar (st[-- top] + '0');
    }
} using namespace FASTIO;
const int MAXN = 5e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, m, A[MAXN];

/* 这辈子没这么讨厌过 DS */

namespace Beats {
    struct Segmentree {
        int l, r, Val, maxfst, maxsec, maxhis, maxCnt;
        int lazy1, lazy2, lazy3, lazy4;  
        /* 1 维护 A 中最大值加的最多的一次，2 维护 B 中的，3 维护 A 中除最大值外的，4 维护 B 中的 */
        void clearLazy() { lazy1 = lazy2 = lazy3 = lazy4 = 0; }
    } Seg[MAXN << 2];
    #define lson rt << 1
    #define rson rt << 1 | 1
    void pushup (int rt) {
        Seg[rt].maxfst = max (Seg[lson].maxfst, Seg[rson].maxfst);
        Seg[rt].maxhis = max (Seg[lson].maxhis, Seg[rson].maxhis);
        Seg[rt].Val = Seg[lson].Val + Seg[rson].Val;
        if (Seg[lson].maxfst == Seg[rson].maxfst) {
            Seg[rt].maxsec = max (Seg[lson].maxsec, Seg[rson].maxsec);
            Seg[rt].maxCnt = Seg[lson].maxCnt + Seg[rson].maxCnt;
        }
        if (Seg[lson].maxfst > Seg[rson].maxfst) {
            Seg[rt].maxsec = max (Seg[lson].maxsec, Seg[rson].maxfst);
            Seg[rt].maxCnt = Seg[lson].maxCnt;
        }
        if (Seg[lson].maxfst < Seg[rson].maxfst) {
            Seg[rt].maxsec = max (Seg[lson].maxfst, Seg[rson].maxsec);
            Seg[rt].maxCnt = Seg[rson].maxCnt;
        }
        return;
    }
    void Build (int l, int r, int rt) {
        Seg[rt].l = l, Seg[rt].r = r;
        if (l == r) {
            Seg[rt].maxfst = Seg[rt].Val = Seg[rt].maxhis = A[l];
            Seg[rt].maxsec = -inf, Seg[rt].maxCnt = 1;
            return;
        }
        int mid = l + r >> 1;
        Build (l, mid, lson), Build (mid + 1, r, rson);
        pushup (rt);
    }
    void update (int rt, int v1, int v2, int v3, int v4) { /* v1 区间 maxfst 加，v2 区间 maxhis 加， v3 区间 maxsec 加，V4 区间 maxhis_sec 加 */
        Seg[rt].Val += (v1 * Seg[rt].maxCnt + v3 * (Seg[rt].r - Seg[rt].l + 1 - Seg[rt].maxCnt));
        Seg[rt].maxhis = max (Seg[rt].maxhis, Seg[rt].maxfst + v2);
        Seg[rt].maxfst += v1;
        if (Seg[rt].maxsec != -inf) Seg[rt].maxsec += v3;
        Seg[rt].lazy2 = max (Seg[rt].lazy2, Seg[rt].lazy1 + v2), Seg[rt].lazy1 += v1;
        Seg[rt].lazy4 = max (Seg[rt].lazy4, Seg[rt].lazy3 + v4), Seg[rt].lazy3 += v3;
        return;
    }
    void pushdown (int rt) {
        int maxVal = max (Seg[lson].maxfst, Seg[rson].maxfst);
        if (maxVal == Seg[lson].maxfst)
            update (lson, Seg[rt].lazy1, Seg[rt].lazy2, Seg[rt].lazy3, Seg[rt].lazy4);
        else
            update (lson, Seg[rt].lazy3, Seg[rt].lazy4, Seg[rt].lazy3, Seg[rt].lazy4);
        if (maxVal == Seg[rson].maxfst)
            update (rson, Seg[rt].lazy1, Seg[rt].lazy2, Seg[rt].lazy3, Seg[rt].lazy4);
        else
            update (rson, Seg[rt].lazy3, Seg[rt].lazy4, Seg[rt].lazy3, Seg[rt].lazy4);
        return Seg[rt].clearLazy();
    }
    void ModifySum (int ql, int qr, int rt, int k) {
        int l = Seg[rt].l, r = Seg[rt].r;
        // if (ql > l || qr < r) return;
        if (ql <= l && qr >= r)
            return update(rt, k, k, k, k);
        int mid = l + r >> 1;
        pushdown (rt);
        if (ql <= mid) 
            ModifySum (ql, qr, lson, k);
        if (qr > mid)
            ModifySum (ql, qr, rson, k);
        pushup (rt);
        return;
    }
    void ModifyMin (int ql, int qr, int rt, int k) {
        int l = Seg[rt].l, r = Seg[rt].r;
        // if (ql > l || qr < r || Seg[rt].maxfst <= k) return;
        if (ql <= l && qr >= r && Seg[rt].maxsec < k) 
            return update (rt, k - Seg[rt].maxfst, k - Seg[rt].maxfst, 0, 0);
        int mid = l + r >> 1;
        pushdown (rt);
        if (ql <= mid)
            ModifyMin (ql, qr, lson, k);
        if (qr > mid)
            ModifyMin (ql, qr, rson, k);
        pushup (rt);
        return;
    }
    int querySum (int ql, int qr, int rt) {
        int l = Seg[rt].l, r = Seg[rt].r;
        // if (ql > l || qr < r) return 0;
        if (ql <= l && qr >= r)
            return Seg[rt].Val;
        int mid = l + r >> 1, tmpSum = 0;
        pushdown (rt);
        if (ql <= mid)
            tmpSum += querySum (ql, qr, lson);
        if (qr > mid)
            tmpSum += querySum (ql, qr, rson);
        return tmpSum;
    }
    int queryMax (int ql, int qr, int rt) {
        int l = Seg[rt].l, r = Seg[rt].r;
        // if (ql > l || qr < r) return -inf;
        if (ql <= l && qr >= r)
            return Seg[rt].maxfst;
        int mid = l + r >> 1, tmpMax = -inf;
        pushdown (rt);
        if (ql <= mid)
            tmpMax = max (tmpMax, queryMax (ql, qr, lson));
        if (qr > mid)
            tmpMax = max (tmpMax, queryMax (ql, qr, rson));
        return tmpMax;
    }
    int queryMax_his (int ql, int qr, int rt) {
        int l = Seg[rt].l, r = Seg[rt].r;
        // if (ql > l || qr < r) return -inf;
        if (ql <= l && qr >= r)
            return Seg[rt].maxhis;
        int mid = l + r >> 1, tmpMax_his = -inf;
        pushdown (rt);
        if (ql <= mid)
            tmpMax_his = max (tmpMax_his, queryMax_his (ql, qr, lson));
        if (qr > mid)
            tmpMax_his = max (tmpMax_his, queryMax_his (ql, qr, rson));
        return tmpMax_his;
    }
} using namespace Beats;

signed main() {
    /*
    freopen ("P6242_1.in","r",stdin);
    freopen ("Ans.out","w",stdout);
    */
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) A[i] = read();
    Build (1, n, 1);
    while (m --) {
        int opt = read(), l = read(), r = read(), k;
        if (opt == 1) {
            k = read();
            ModifySum (l, r, 1, k);
        }
        if (opt == 2) {
            k = read();
            ModifyMin (l, r, 1, k);
        }
        if (opt == 3) 
            write (querySum (l, r, 1)), putchar ('\n');
        if (opt == 4)
            write (queryMax (l, r, 1)), putchar ('\n');
        if (opt == 5)
            write (queryMax_his (l, r, 1)), putchar ('\n');
    }
    return 0;
}