#pragma GCC optimize("O3")
#include <bits/allocator.h>
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using p2 = pair<ll, ll>;
const ll inf = 1e18;

#define repe(i, arr) for (auto& i : arr)
#define rep(i, b) for(ll i = 0; i < (b); ++i)
#define repp(i, a, b) for(ll i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) ((ll)x.size())

namespace lines {
    using big_signed = __int128;

    struct Line {
        short k;  // slopes bounded by blocksize, int suffices
        ll m;   // y = kx + m
        bool operator<(const Line& o) const {
            return k < o.k;
        }
        Line operator+(const Line& other) const {
            return { (short)(k + other.k), m + other.m };
        }
        ll eval(ll x) const {
            return k * x + m;
        }
    };

    bool better(const Line& a, const Line& b, ll x) {
        return a.eval(x) >= b.eval(x);
    }

    ll eval(const vector<Line>& sp, ll x) {
        int l = 0, r = sp.size() - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (better(sp[m], sp[m + 1], x)) r = m;
            else l = m + 1;
        }
        return sp[l].eval(x);
    }

    inline bool intersection_geq(const Line& A, const Line& B, const Line& C) {
        auto left = (big_signed)(B.m - A.m) * (A.k - C.k);
        auto right = (big_signed)(C.m - A.m) * (A.k - B.k);
        return left >= right;
    }

    void hullify_vector(vector<Line>& lines)
    {
        int hsz = 0;
        for (auto& l : lines) {
            while (hsz >= 2 && intersection_geq(lines[hsz - 2], lines[hsz - 1], l)) {
                --hsz;
            }
            lines[hsz++] = l;
        }

        lines.resize(hsz);
    }

    bool intersect_less(const Line& a1, const Line& a2, const Line& b1, const Line& b2) {
        big_signed numA = (big_signed)a2.m - (big_signed)a1.m;
        big_signed denA = (big_signed)a1.k - (big_signed)a2.k;
        big_signed numB = (big_signed)b2.m - (big_signed)b1.m;
        big_signed denB = (big_signed)b1.k - (big_signed)b2.k;
        return numA * denB < numB * denA;
    }

    void minkowski_sum_dense(vector<ll>& res, const vector<Line>& A, const vector<Line>& B) {
        int i = 0, j = 0, n = (int)A.size(), m = (int)B.size();
        while (i < n && j < m) {
            Line l = A[i] + B[j];
            res[l.k] = max(res[l.k], l.m);
            if (i + 1 == n) ++j;
            else if (j + 1 == m) ++i;
            else (intersect_less(A[i], A[i + 1], B[j], B[j + 1]) ? i : j)++;
        }
        while (i < n) { Line l = A[i++] + B.back(); res[l.k] = max(res[l.k], l.m); }
        while (j < m) { Line l = A.back() + B[j++]; res[l.k] = max(res[l.k], l.m); }
    }

    struct Tree
    {
        int blocksize;
        vector<ll> lazy;
        span<ll> block;
        vector<vector<Line>> pref;
        vector<vector<Line>> suf;
        vector<vector<ll>> all_m; // dense: all lines. all_m[x][k] = max m for kx+m in node x
        vector<Line> all_lines_root;
        bool root_dirty = true;
        vector<ll> tot;
        Tree() {}
        Tree(int blocksize, vi& blockv) : blocksize(blocksize), lazy(blocksize * 2), block(span<ll>(all(blockv))),
            pref(blocksize * 2), suf(blocksize * 2), all_m(blocksize * 2),
            tot(blocksize * 2)
        {
            build(1, 0, blocksize - 1);
        }

        void rebuild_node(int x, int l, int r)
        {
            int width = r - l + 1;
            int lsz, rsz;

            // Build pref
            lsz = pref[x * 2].size();
            rsz = pref[x * 2 + 1].size();
            pref[x].resize(lsz + rsz);
            memcpy(pref[x].data(), pref[x * 2].data(), lsz * sizeof(Line));
            memcpy(pref[x].data() + lsz, pref[x * 2 + 1].data(), rsz * sizeof(Line));
            for (int i = lsz; i < lsz + rsz; i++) {
                pref[x][i].k += width / 2;
                pref[x][i].m += tot[x * 2];
            }
            hullify_vector(pref[x]);

            lsz = suf[x * 2 + 1].size();
            rsz = suf[x * 2].size();
            suf[x].resize(lsz + rsz);
            memcpy(suf[x].data(), suf[x * 2 + 1].data(), lsz * sizeof(Line));
            memcpy(suf[x].data() + lsz, suf[x * 2].data(), rsz * sizeof(Line));
            for (int i = lsz; i < lsz + rsz; i++) {
                suf[x][i].k += width / 2;
                suf[x][i].m += tot[x * 2 + 1];
            }
            hullify_vector(suf[x]);

            all_m[x].assign(width + 1, -inf);
            all_m[x][0] = 0;

            minkowski_sum_dense(all_m[x], suf[x * 2], pref[x * 2 + 1]);

            ll* __restrict dst = all_m[x].data();
            const ll* __restrict lsrc = all_m[x * 2].data();
            const ll* __restrict rsrc = all_m[x * 2 + 1].data();

            int left_width = width / 2;
            rep(k, left_width + 1) {
                dst[k] = max({dst[k], lsrc[k], rsrc[k]});
            }

            tot[x] = tot[x * 2] + tot[x * 2 + 1];
            if (x == 1) root_dirty = true;
        }

        void build(int x, int l, int r)
        {
            if (l == r) {
                tot[x] = block[l];
                pref[x] = { {1,block[l]} };
                suf[x] = { {1,block[l]} };
                all_m[x] = { 0, block[l] };
                return;
            }

            int mid = (l + r) / 2;
            build(x * 2, l, mid);
            build(x * 2 + 1, mid + 1, r);

            int width = r - l + 1;
            pref[x].reserve(width);
            suf[x].reserve(width);
            rebuild_node(x, l, r);
        }

        void hullify_root() {
            if (!root_dirty) return;
            all_lines_root.clear();
            for (int k = 0; k < (int)all_m[1].size(); k++) {
                if (all_m[1][k] > -inf) {
                    all_lines_root.push_back({(short)k, all_m[1][k]});
                }
            }
            hullify_vector(all_lines_root);
            root_dirty = false;
        }

        vector<Line>& get_all_lines() {
            hullify_root();
            return all_lines_root;
        }

        void reset()
        {
            rep(i, sz(lazy)) lazy[i] = 0;
            build(1, 0, blocksize - 1);
            root_dirty = true;
        }

        inline void put_tag(int x, int width, ll w)
        {
            if (!w) return;
            tot[x] += w * width;
            ll* __restrict am = all_m[x].data();
            rep(k, width + 1) am[k] += (ll)k * w;
            repe(l, pref[x]) l.m += l.k * w;
            repe(l, suf[x]) l.m += l.k * w;
            lazy[x] += w;
            if (x == 1) root_dirty = true;
        }

        void add(int x, int l, int r, int ql, int qr, ll w, ll inherited=0)
        {
            int width = r - l + 1;
            if (r < ql || l > qr)
            {
                put_tag(x, width, inherited);
                return;
            }
            if (l >= ql && r <= qr)
            {
                put_tag(x, width, inherited + w);
                return;
            }

            int mid = (l + r) / 2;
            add(x * 2, l, mid, ql, qr, w, inherited + lazy[x]);
            add(x * 2 + 1, mid + 1, r, ql, qr, w, inherited + lazy[x]);
            lazy[x] = 0;

            // forced to rebuild
            rebuild_node(x, l, r);
        }
    };
};

using lines::Line;

struct Blockres
{
    ll sum = 0, prefmax = 0, sufmax = 0, ans = 0;
    Blockres() {}
    Blockres(ll val) : sum(val), prefmax(max(0LL, val)), sufmax(max(0LL, val)), ans(max(0LL, val)) {}
    Blockres(ll sum, ll prefmax, ll sufmax, ll ans) : sum(sum), prefmax(prefmax), sufmax(sufmax), ans(ans) {}
    Blockres merge(Blockres o)
    {
        Blockres ret = *this;
        ret.ans = max({ ret.ans, o.ans, ret.sufmax + o.prefmax });
        ret.prefmax = max(ret.prefmax, ret.sum + o.prefmax);
        ret.sufmax = max(o.sufmax, o.sum + ret.sufmax);
        ret.sum += o.sum;
        return ret;
    }
};

vector<Blockres> answers;
vi arr;
struct Blockdata
{
    int bl, br;
    ll lazy_add = 0;
    ll tot = 0;
    int blocksize;
    vi block;
    Blockdata(int blocksize) : blocksize(blocksize), block(blocksize) {}

    void reset(int bl, int br)
    {
        this->bl = bl;
        this->br = br;
        lazy_add = 0;

        rep(i, blocksize) block[i] = arr[i + bl];
        tot = accumulate(all(block), 0LL);

        update_hull(0, blocksize - 1, 0, true);
    }

    lines::Tree ans_hull;

    void update_hull(int l, int r, ll w, bool rebuild = false)
    {
        if (!sz(ans_hull.lazy) || rebuild)
        {
            if (!sz(ans_hull.lazy)) ans_hull = lines::Tree(blocksize, block);
            else ans_hull.reset();
        }
        else
        {
            ans_hull.add(1, 0, blocksize - 1, l - bl, r - bl, w);
        }
    }

    void handle_partial_update(int l, int r, ll w)
    {
        // update block and tot incrementally
        tot += lazy_add * blocksize;
        rep(i, blocksize) block[i] += lazy_add;

        int cnt = min(r + 1, br) - max(l, bl);
        tot += w * cnt;
        repp(i, max(l, bl), min(r + 1, br)) block[i - bl] += w;

        ans_hull.add(1, 0, blocksize - 1, 0, blocksize - 1, lazy_add);

        lazy_add = 0;
        update_hull(l, r, w);
    }

    vector<pair<ll,int>> waiting_full;

    inline ll div(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    void solve_big()
    {
        static vector<ll> xright_all, xright_pref, xright_suf;

        auto compute_xright = [&](const vector<Line>& lines, vector<ll>& out) {
            out.clear();
            for (int i = 0; i + 1 < (int)lines.size(); i++) {
                const Line& a = lines[i];
                const Line& b = lines[i + 1];
                if (a.k != b.k) {
                    ll x = div(b.m - a.m, a.k - b.k);
                    out.push_back(x);
                }
            }
        };

        auto& all_hull = ans_hull.get_all_lines();
        auto& pref_hull = ans_hull.pref[1];
        auto& suf_hull = ans_hull.suf[1];

        compute_xright(all_hull, xright_all);
        compute_xright(pref_hull, xright_pref);
        compute_xright(suf_hull, xright_suf);

        for (auto [lazy, q_ind] : waiting_full)
        {
            int idx = upper_bound(all(xright_all), lazy) - xright_all.begin();
            ll bestinside = all_hull[idx].eval(lazy);

            idx = upper_bound(all(xright_pref), lazy) - xright_pref.begin();
            ll bestpref = pref_hull[idx].eval(lazy);

            idx = upper_bound(all(xright_suf), lazy) - xright_suf.begin();
            ll bestsuf = suf_hull[idx].eval(lazy);

            Blockres blockres(tot + lazy * blocksize, bestpref, bestsuf, bestinside);
            answers[q_ind] = answers[q_ind].merge(blockres);
        }

        waiting_full.clear();
    }

    void pop_queries()
    {
        if (sz(waiting_full) == 0) return;
        if (sz(waiting_full) > 1000)
        {
            solve_big();
            return;
        }

        auto& all_hull = ans_hull.get_all_lines();
        auto& pref_hull = ans_hull.pref[1];
        auto& suf_hull = ans_hull.suf[1];

        for (auto [lazy, q_ind] : waiting_full)
        {
            ll bestinside = lines::eval(all_hull, lazy);
            ll bestpref = lines::eval(pref_hull, lazy);
            ll bestsuf = lines::eval(suf_hull, lazy);

            Blockres block(tot + lazy * blocksize, bestpref, bestsuf, bestinside);
            answers[q_ind] = answers[q_ind].merge(block);
        }
        waiting_full.clear();
    }
};


struct Query
{
    bool update : 1;
    unsigned int l : 19;
    unsigned int r : 19;
    int w : 25;
};

vector<Blockres> solve(vi arrin, vector<Query> queries, int blocksize)
{
    int n = sz(arrin);
    arr = arrin;
    int numq = 0;
    for (auto [upd, l, r, w] : queries)
    {
        if (!upd) numq++;
    }
    answers.resize(numq);
    int numblocks = n / blocksize;

    Blockdata currblock(blocksize);
    rep(b, numblocks)
    {
        unsigned int bl = b * blocksize;
        unsigned int br = (b + 1) * blocksize;
        currblock.reset(bl, br);

        auto fully_outside = [&](int l, int r)
        {
            if (r < bl || l >= br) return true;
            return false;
        };
        auto fully_inside = [&](int l, int r)
        {
            if (bl >= l && br - 1 <= r) return true;
            return false;
        };

        auto update_hull = [&](int l, int r, ll w)
        {
            currblock.handle_partial_update(l, r, w);
        };
        update_hull(0, 0, 0);

        int qind = -1;

        for (auto [upd, l, r, w] : queries)
        {
            if (!upd) qind++;
            if (fully_outside(l, r)) continue;
            if (fully_inside(l, r))
            {
                if (upd)
                {
                    currblock.lazy_add += w;
                }
                else
                {
                    currblock.waiting_full.emplace_back(currblock.lazy_add, qind);
                }
            }
            else // partially inside
            {
                if (upd)
                {
                    // pop all waiting queries
                    currblock.pop_queries();

                    update_hull(l, r, w);
                }
                else // partially inside query: handle naive
                {
                    repp(i, max(l, bl), min(r + 1u, br))
                    {
                        ll val = currblock.block[i - bl] + currblock.lazy_add;
                        answers[qind] = answers[qind].merge(Blockres(val));
                    }
                }
            }
        }
        currblock.pop_queries();
    }

    return answers;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vi arr(n);
    rep(i, n) cin >> arr[i];

    int numq = 0;
    vector<Query> queries;
    queries.reserve(q);
    rep(i, q)
    {
        char c;
        cin >> c;
        if (c == '+')
        {
            unsigned int l, r;
            int w;
            cin >> l >> r >> w;
            l--; r--;
            Query qu = { 1,l,r,w };
            queries.push_back(qu);
        }
        else
        {
            unsigned int l, r;
            cin >> l >> r;
            l--; r--;
            numq++;
            Query qu = { 0, l,r,0 };
            queries.push_back(qu);
        }
    }

    int blocksize = 512; // For some reason, a const blocksize is slower

    while (sz(arr) % (blocksize) != 0)
    {
        n++;
        arr.push_back(0);
    }

    vector<Blockres> ans = solve(arr, queries, blocksize);

    rep(i, sz(ans))
    {
        cout << ans[i].ans << '\n';
    }

    return 0;
}