#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
using namespace std;
#define ix(l, r) ((l + r) | (l != r))
#define mp(i, j) (make_pair(i, j))
typedef long long ll;
const int N = 5e5+5;
const int qwq = 2e9;
int n, m, w, l, r, op;

struct node {
    ll sum;
    int maxa, cnt, maxb, maxc;
    int add1, add2, add3, add4;
}tr[N<<1];

inline void push_up (int l, int r) {
    int mid = (l + r) >> 1;
    int rt = ix(l, r), ls = ix(l, mid), rs = ix(mid + 1, r);
    tr[rt].sum = tr[ls].sum + tr[rs].sum;
    tr[rt].maxc = max(tr[ls].maxc, tr[rs].maxc);
    tr[rt].maxa = max(tr[ls].maxa, tr[rs].maxa);
    if(tr[ls].maxa == tr[rs].maxa) {
        tr[rt].cnt = tr[ls].cnt + tr[rs].cnt;
        tr[rt].maxb = max(tr[ls].maxb, tr[rs].maxb);
    }
    else if(tr[ls].maxa > tr[rs].maxa) {
        tr[rt].cnt = tr[ls].cnt;
        tr[rt].maxb = max(tr[ls].maxb, tr[rs].maxa);
    }
    else {
        tr[rt].cnt = tr[rs].cnt;
        tr[rt].maxb = max(tr[ls].maxa, tr[rs].maxb);
    }
}

void build (int l, int r) {
    if(l == r) {
        cin >> w;
        tr[ix(l, r)] = (node){w, w, 1, -qwq, w, 0, 0, 0, 0};
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid), build(mid + 1, r);
    return push_up(l, r);
}

inline void change (int k1, int k2, int k3, int k4, int l, int r) {
    int rt = ix(l, r);
    tr[rt].sum += 1ll * k1 * tr[rt].cnt + 1ll * k2 * (r - l + 1 - tr[rt].cnt);
    tr[rt].maxc = max(tr[rt].maxc, tr[rt].maxa + k3);
    tr[rt].add3 = max(tr[rt].add3, tr[rt].add1 + k3);
    tr[rt].add4 = max(tr[rt].add4, tr[rt].add2 + k4);
    tr[rt].add1 += k1;
    tr[rt].maxa += k1;
    tr[rt].add2 += k2;
    if(tr[rt].maxb != -qwq) tr[rt].maxb += k2;
}

inline void push_down (int l, int r) {
    int mid = (l + r) >> 1;
    int rt = ix(l, r), ls = ix(l, mid), rs = ix(mid + 1, r);
    int res = max(tr[ls].maxa, tr[rs].maxa);
    if(tr[ls].maxa == res) 
        change(tr[rt].add1, tr[rt].add2, tr[rt].add3, tr[rt].add4, l, mid);
    else change(tr[rt].add2, tr[rt].add2, tr[rt].add3, tr[rt].add4, l, mid);
    if(tr[rs].maxa == res) 
        change(tr[rt].add1, tr[rt].add2, tr[rt].add3, tr[rt].add4, mid + 1, r);
    else change(tr[rt].add2, tr[rt].add2, tr[rt].add3, tr[rt].add4, mid + 1, r);
    tr[rt].add1 = tr[rt].add2 = tr[rt].add3 = tr[rt].add4 = 0;
}

ll query_sum (int l, int r, int dl, int dr) {
    if(dr < l || r < dl) return 0;
    if(dl <= l && r <= dr) return tr[ix(l, r)].sum;
    int mid = (l + r) >> 1;
    push_down(l, r);
    return query_sum(l, mid, dl, dr) + query_sum(mid + 1, r, dl, dr);
}

int query_maxa (int l, int r, int dl, int dr) {
    if(dr < l || r < dl) return -qwq;
    if(dl <= l && r <= dr) return tr[ix(l, r)].maxa;
    int mid = (l + r) >> 1;
    push_down(l, r);
    return max(query_maxa(l, mid, dl, dr), query_maxa(mid + 1, r, dl, dr));
}

int query_maxc (int l, int r, int dl, int dr) {
    if(dr < l || r < dl) return -qwq;
    if(dl <= l && r <= dr) return tr[ix(l, r)].maxc;
    int mid = (l + r) >> 1;
    push_down(l, r);
    return max(query_maxc(l, mid, dl, dr), query_maxc(mid + 1, r, dl, dr));
}

void update_add (int l, int r, int dl, int dr, int k) {
    if(dr < l || r < dl) return ;
    if(dl <= l && r <= dr) return change(k, k, k, k, l, r);
    int mid = (l + r) >> 1;
    push_down(l, r);
    update_add(l, mid, dl, dr, k), update_add(mid + 1, r, dl, dr, k);
    return push_up(l, r);
}

void update_min (int l, int r, int dl, int dr, int k) {
    if(dr < l || r < dl || k >= tr[ix(l, r)].maxa) return ;
    if(dl <= l && r <= dr && k > tr[ix(l, r)].maxb) return change(k - tr[ix(l, r)].maxa, 0, k - tr[ix(l, r)].maxa, 0, l, r);
    int mid = (l + r) >> 1;
    push_down(l, r);
    update_min(l, mid, dl, dr, k), update_min(mid + 1, r, dl, dr, k);
    return push_up(l, r);
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    build(1, n);
    while(m--) {
        cin >> op >> l >> r;
        if(op == 1) {
            cin >> w;
            update_add(1, n, l, r, w);
        }
        else if(op == 2) {
            cin >> w;
            update_min(1, n, l, r, w);
        }
        else if(op == 3) {
            cout << query_sum(1, n, l, r) << "\n";
        }
        else if(op == 4) {
            cout << query_maxa(1, n, l, r) << "\n";
        }
        else cout << query_maxc(1, n, l, r) << "\n";
    }
    return 0;
}