#include <bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[next(L)==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
#define int ll
// now inf is big enough
const int MAX_N = 300010;
const ll inf = 1ll << 55;
// !Warning, you should update after push in 吉如一

ll n, a[MAX_N], q;

struct node {
    ll mx, sec, cntmx, len, sum, at, mt;
    node(ll v = 0) {
        mx = sum = v;
        sec = -inf;
        mt = inf;
        len = cntmx = 1;
        at = 0;
    }
    void operator += (ll v) {
        mx += v, sec += v, sum += v * len, at += v, mt += v;
    }
    // return true if need push
    bool chmn(ll v) {
        if (v >= mx) return false;
        assert(v <= mt);
        sum -= (mx - v) * cntmx;
        mt = mx = v;
        return sec <= v && cntmx < len;
    }
    void updatemx(node a) {
        if (chmax(mx, a.mx)) {
            cntmx = a.cntmx;
            chmax(sec, a.sec);
        }
        else if (mx == a.mx)
            cntmx += a.cntmx;
        else chmax(sec, a.mx);
    }
    node (node a, node b) :
        mx(-inf), sec(-inf), cntmx(0), len(a.len + b.len), sum(a.sum + b.sum), at(0), mt(inf) {
            updatemx(a), updatemx(b);
        }
};

void brutemn(int l, int r, int x) {
    for (int i = l;i < r;++i)
        chmin(a[i], x);
}
void brutead(int l, int r, int x) {
    for (int i = l;i < r;++i)
        a[i] += x;
}
ll brutesum(int l, int r) {
    ll res = 0;
    for (int i = l;i < r;++i)
        res += a[i];
    return res;
}
ll brutemx(int l, int r) {
    ll res = 0;
    for (int i = l;i < r;++i)
        chmax(res, a[i]);
    return res;
}

struct sgt {
    vector<node> val;
    int n;
    void update(int i) {
        if (i >= n || i == 0) return;
        ll &at = val[i].at, &mt = val[i].mt;
        if (at) {
            val[i<<1] += at;
            val[i<<1|1] += at;
            at = 0;
        }
        if (mt < inf) {
            if (val[i<<1].chmn(mt))
                update(i<<1);
            if (val[i<<1|1].chmn(mt))
                update(i<<1|1);
        }

        val[i] = node(val[i<<1], val[i<<1|1]);

        assert(at == 0 && mt == inf);
    }
    // Yes I have cleared add tag and chmin tag
    sgt(int _n) : n(_n) {
        val.resize(n<<1);
        for (int i = 0;i < n;++i)
            val[i + n] = node(a[i]);
        for (int i = n-1;i > 0;--i)
            update(i);
    }
    void pa(int p) {
        for (int i = 18;i > 0;--i)
            update(p >> i);
    }
    void smn(int i, int x) {
        if (val[i].chmn(x))
            update(i);
    }
    void chmnlr(int l, int r, int x) {
        l += n, r += n;
        pa(l), pa(r-1);
        int sl = l, sr = r-1;
        for (;l < r;l>>=1, r>>=1) {
            if (l&1) smn(l++, x);
            if (r&1) smn(--r, x);
        }
        for (;sl >>= 1, sr >>= 1;) {
            update(sl), update(sr);
        }
    }
    void addlr(int l, int r, int x) {
        l += n, r += n;
        pa(l), pa(r-1);
        int sl = l, sr = r-1;
        for (;l < r;l>>=1, r>>=1) {
            if (l&1) val[l++] += x;
            if (r&1) val[--r] += x;
        }
        for (;sl >>= 1, sr >>= 1;) {
            update(sl), update(sr);
        }

    }
    node qry(int l, int r) {

        l += n, r += n;
        pa(l), pa(r-1);
        node res(0);
        for (;l < r;l>>=1, r>>=1) {
            if (l&1) res = node(res, val[l++]);
            if (r&1) res = node(res, val[--r]);
        }
        return res;
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 0;i < n;++i)
        cin >> a[i];

    sgt tree(n);
    ll out = -1;
    while (q--) {
        int t, l, r, x;
        cin >> t >> l >> r; --l;

        if (t <= 2) {
            cin >> x;
            if (t == 1) tree.chmnlr(l, r, x);
            if (t == 2) tree.addlr(l, r, x);
        }
        else {
            auto res = tree.qry(l, r);
            if (t == 3) cout << res.sum << '\n', out = res.sum;
            if (t == 4) cout << res.mx << '\n', out = res.mx;
        }

#ifdef KEV
        DE(t, l, r, x);
        if (t == 1) brutemn(l, r, x);
        if (t == 2) brutead(l, r, x);
        if (t == 3) {
            DE(brutesum(l, r), out);
            assert(brutesum(l, r) == out);
        }
        if (t == 4) {
            DE(brutemx(l, r), out);
            assert(brutemx(l, r) == out);
        }
//      const int len = 3;
//      for (int i = 0;i < n;++i) {
//          assert(tree.qry(i, i+1).sum == brutesum(i, i+1));
//      }
#endif
//
////        DE(t, l, r, x);
//      for (int i = 0;i < n;++i)
//          cerr << tree.qry(i, i+1).sum << " \n"[i==n];
//
//      cerr << endl;
//      cout << endl;
    }
}