#include <bits/stdc++.h>
#define PII pair <int, int>
#define ll long long
#define int long long
#define MP make_pair
#define PB push_back
using namespace std;
constexpr int N = 5e5 + 10, INF = 2e9;
int n, m, a[N];
//快读快写
char *p1, *p2, buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read ()
{
	int x = 0, f = 1;
	char ch = nc ();
	while (ch < 48 || ch > 57)
	{
		if (ch == '-') f = -1;
		ch = nc ();
	}
	while (48 <= ch && ch <= 57) x = x * 10 + ch - 48, ch = nc ();
	return x * f;
}
void write (int x)
{
    if (x < 0) putchar ('-'), x = -x;
    if (x > 9) write (x / 10);
    putchar (x % 10 + '0');
}
//线段树
struct node
{
    int l, r, mxa, sub, add1, add2, add3, add4, cnt, sum, mxb;
    #define l(p) t[p].l //左端点
    #define r(p) t[p].r //右端点
    #define mxa(p) t[p].mxa //最大
    #define mxb(p) t[p].mxb //历史最大
    #define sub(p) t[p].sub //次大
    #define add1(p) t[p].add1 //最大的lazytag
    #define add2(p) t[p].add2 //其他的lazytag
    #define add3(p) t[p].add3 //历史最大的最大的lazytag
    #define add4(p) t[p].add4 //历史最大的其他的lazytag
    #define cnt(p) t[p].cnt //最大值的数量
    #define sum(p) t[p].sum //区间和
} t[4 * N];
inline void pushup (int p) 
{
    int ls = p << 1, rs = p << 1 | 1;
    sum (p) = sum (ls) + sum (rs);
    mxa (p) = max (mxa (ls), mxa (rs));
    mxb (p) = max (mxb (ls), mxb (rs));
    if (mxa (ls) == mxa (rs)) {cnt (p) = cnt (ls) + cnt (rs); sub (p) = max (sub (ls), sub (rs));}
    else if (mxa (ls) > mxa (rs)) {cnt (p) = cnt (ls), sub (p) = max (sub (ls), mxa (rs));}
    else {cnt (p) = cnt (rs), sub (p) = max (sub (rs), mxa (ls));}
}
//方便进行pushdown的函数
inline void spread (int p, int k1, int k2, int k3, int k4)
{
    sum (p) += (k1 * cnt (p) + k2 * (r (p) - l (p) + 1 - cnt (p)));
    mxb (p) = max (mxb (p), mxa (p) + k3);
    mxa (p) += k1;
    if (sub (p) != -INF) sub (p) += k2;
    add3 (p) = max (add3 (p), k3 + add1 (p));
    add4 (p) = max (add4 (p), k4 + add2 (p));
    add1 (p) += k1, add2 (p) += k2;
}
inline void pushdown (int p)
{
    int ls = p << 1, rs = p << 1 | 1, mx = max (mxa (ls), mxa (rs));
    if (mxa (ls) == mx) spread (ls, add1 (p), add2 (p), add3 (p), add4 (p));
    else spread (ls, add2 (p), add2 (p), add4 (p), add4 (p));
    if (mxa (rs) == mx) spread (rs, add1 (p), add2 (p), add3 (p), add4 (p));
    else spread (rs, add2 (p), add2 (p), add4 (p), add4 (p));
    add1 (p) = add2 (p) = add3 (p) = add4 (p) = 0;
}
//建树
void build (int p, int l, int r)
{
    l (p) = l, r (p) = r;
    if (l == r) {mxa (p) = mxb (p) = sum (p) = a[l]; cnt (p) = 1; sub (p) = -INF; return;}
    int mid = (l + r) >> 1;
    build (p << 1, l, mid);
    build (p << 1 | 1, mid + 1, r);
    pushup (p);
}
//区间加
void change_add (int p, int l, int r, int x)
{
    if (l <= l (p) && r (p) <= r) 
    {
        sum (p) += (r (p) - l (p) + 1) * x;
        mxa (p) += x; sub (p) += (sub (p) != -INF ? x : 0); add1 (p) += x; add2 (p) += x;
        add3 (p) = max (add3 (p), add1 (p)); add4 (p) = max (add4 (p), add2 (p)); mxb (p) = max (mxb (p), mxa (p));
        return;
    }
    int mid = (l (p) + r (p)) >> 1;
    pushdown (p);
    if (mid >= l) change_add (p << 1, l, r, x);
    if (mid < r) change_add (p << 1 | 1, l, r, x);
    pushup (p);
}
//区间取min
void change_min (int p, int l, int r, int x)
{
    if (x >= mxa (p)) return;
    if (l <= l (p) && r (p) <= r && sub (p) < x)
    {
        sum (p) -= cnt (p) * (mxa (p) - x); add1 (p) -= (mxa (p) - x); mxa (p) = x;
        return;
    }
    pushdown (p);
    int mid = (l (p) + r (p)) >> 1;
    if (mid >= l) change_min (p << 1, l, r, x);
    if (mid < r) change_min (p << 1 | 1, l, r, x);
    pushup (p);
}
//查询区间和
int query_sum (int p, int l, int r)
{
    if (l <= l (p) && r (p) <= r) {return sum (p);}
    int num = 0, mid = (l (p) + r (p)) >> 1;
    pushdown (p);
    if (mid >= l) num += query_sum (p << 1, l, r);
    if (mid < r) num += query_sum (p << 1 | 1, l, r);
    return num;
}
//查询最大值
int query_mxa (int p, int l, int r)
{
    if (l <= l (p) && r (p) <= r) {return mxa (p);}
    int num = -INF, mid = (l (p) + r (p)) >> 1;
    pushdown (p);
    if (mid >= l) num = max (num, query_mxa (p << 1, l, r));
    if (mid < r) num = max (num, query_mxa (p << 1 | 1, l, r));
    return num;
}
//查询历史最大值
int query_mxb (int p, int l, int r)
{
    if (l <= l (p) && r (p) <= r) {return mxb (p);}
    int num = -INF, mid = (l (p) + r (p)) >> 1;
    pushdown (p);
    if (mid >= l) num = max (num, query_mxb (p << 1, l, r));
    if (mid < r) num = max (num, query_mxb (p << 1 | 1, l, r));
    return num;
}
signed main()
{
    n = read (), m = read ();
    for (int i = 1; i <= n; i++) a[i] = read ();
    build (1, 1, n);
    while (m--)
    {
        int op, l, r, k;
        op = read (), l = read (), r = read ();
        if (op == 1) {k = read (); change_add (1, l, r, k);}
        else if (op == 2) {k = read (); change_min (1, l, r, k);}
        else if (op == 3) {write (query_sum (1, l, r)); putchar ('\n');}
        else if (op == 4) {write (query_mxa (1, l, r)); putchar ('\n');}
        else {write (query_mxb (1, l, r)); putchar ('\n');}
    }
    return 0;
}
/*
3 5
11 39 45 
2 2 3
3 1 2 -100
3 2 3 80
2 2 3
1 1 2
*/