#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e7 + 5;
const int inf = 2e9;

int n, m, op, l, r, k;

struct SegmentTree
{
    int sum;
    int l, r, maxx, cnt, cmax, hmax;
    int add1, add2, add3, add4;
} t[N];

inline int read()
{
    int x = 0, falg = 0;
    char c = getchar();
    while (c > '9' || c < '0')
    {
        if (c == '-')
            falg = 1;
        c = getchar();
    }
    while (c <= '9' && c >= '0')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return falg ? -x : x;
}

void push_up(int u)
{
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
    t[u].maxx = max(t[u << 1].maxx, t[u << 1| 1].maxx);
    t[u].hmax = max(t[u << 1].hmax, t[u << 1 | 1].hmax);
    if (t[u << 1].maxx = t[u << 1 | 1].maxx)
    {
        t[u].cmax = max(t[u << 1].cmax, t[u << 1 | 1].cmax);
        t[u].cnt = t[u << 1].cnt + t[u << 1 | 1].cnt;
    }
    else if (t[u << 1].maxx > t[u << 1 | 1].maxx)
    {
        t[u].cmax = max(t[u << 1].cmax, t[u << 1 | 1].maxx);
        t[u].cnt = t[u << 1].cnt;
    }
    else
    {
        t[u].cmax = max(t[u << 1].maxx, t[u << 1 | 1].cmax);
        t[u].cnt = t[u << 1 | 1].cnt;
    }
}

void build(int p, int l, int r)
{
    t[p].l = l;
    t[p].r = r;
    if (l == r)
    {
        t[p].sum = t[p].maxx = t[p].hmax = read();
        t[p].cnt = 1;
        t[p].cmax = -inf;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
}

void change(int p, int k1, int k2, int k3, int k4)
{
    t[p].sum += k1 * t[p].cnt + k2 * (t[p].r - t[p].l + 1 - t[p].cnt);
    t[p].hmax = max(t[p].hmax, t[p].maxx + k3);
    t[p].add3 = max(t[p].add3, t[p].add1 + k3);
    t[p].add4 = max(t[p].add4, t[p].add2 + k4);
    t[p].maxx += k1;
    t[p].add1 += k1;
    t[p].add2 += k2;
    if (t[p].cmax != -inf)
    {
        t[p].cmax += k2;
    }
}

void push_down(int u)
{
    int maxn = max(t[u << 1].maxx, t[u << 1 | 1].maxx);

    if (t[u << 1].maxx == maxn)
    {
        change(u << 1, t[u].add1, t[u].add2, t[u].add3, t[u].add4);
    }
    else
    {
        change(u << 1, t[u].add2, t[u].add2, t[u].add4, t[u].add4);
    }

    if (t[u << 1 | 1].maxx == maxn)
    {
        change(u << 1 | 1, t[u].add1, t[u].add2, t[u].add3, t[u].add4);
    }
    else
    {
        change(u << 1 | 1, t[u].add2, t[u].add2, t[u].add4, t[u].add4);
    }

    t[u].add1 = t[u].add2 = t[u].add3 = t[u].add4 = 0;
}

void update_add(int u)
{
    if (l > t[u].r || t[u].l > r)
    {
        return;
    }
    if (l <= t[u].l && t[u].r <= r)
    {
        change(u, k, k, k, k);
        return;
    }
    push_down(u);
    update_add(u << 1);
    update_add(u << 1 | 1);
    push_up(u);
}

void update_min(int u)
{
    if (l > t[u].r || t[u].l > r || k >= t[u].maxx)
    {
        return;
    }
    if (l <= t[u].l && t[u].r <= r && k > t[u].cmax)
    {
        change(u, k - t[u].maxx, 0, k - t[u].maxx, 0);
        return;
    }
    push_down(u);
    update_min(u << 1);
    update_min(u << 1 | 1);
    push_up(u);
}

int query_sum(int u)
{
    if (l > t[u].r || t[u].l > r)
    {
        return 0;
    }
    if (l <= t[u].l && t[u].r <= r)
    {
        return t[u].sum;
    }
    push_down(u);
    return query_sum(u << 1) + query_sum(u << 1 | 1);
}

int query_maxx(int u)
{
    if (l > t[u].r || t[u].l > r)
    {
        return -inf;
    }
    if (l <= t[u].l && t[u].r <= r)
    {
        return t[u].maxx;
    }
    push_down(u);
    return max(query_maxx(u << 1), query_maxx(u << 1 | 1));
}

int query_hmax(int u)
{
    if (l > t[u].r || t[u].l > r)
    {
        return -inf;
    }
    if (l <= t[u].l && t[u].r <= r)
    {
        return t[u].hmax;
    }
    push_down(u);
    return max(query_hmax(u << 1), query_hmax(u << 1 | 1));
}

signed main()
{
    n = read();
    m = read();
    build(1, 1, n);
    while (m--)
    {
        op = read();
        l = read();
        r = read();

        if (op == 1)
        {
            k = read();
            update_add(1);
        }

        if (op == 2)
        {
            k = read();
            update_min(1);
        }

        if (op == 3)
        {
            cout << query_sum(1) << endl;
        }

        if (op == 4)
        {
            cout << query_maxx(1) << endl;
        }

        if (op == 5)
        {
            cout << query_hmax(1);
        }
    }

    return 0;
}