// /qq Madoka Kaname

#include <bits/stdc++.h>

using namespace std;

#define int long long
constexpr int MAXN=2e5+10;


struct op { int t, x, y; };
int a[MAXN]; vector<op> q; int n, m;
using db=double;
namespace solve_sub1 {
    struct fun { 
        int k, b; 
        int operator()(int x) const { return k*x+b; }
    }; 
    db point(fun a, fun b) {
        return (a.b-b.b)/db(b.k-a.k);
    }
    int tot=0;
    struct SG {
        #define ll(p) tr[p].l
        #define rr(p) tr[p].r
        #define convex(p) tr[p].convex
        #define sum(p) tr[p].sum
        #define val(p) tr[p].val
        #define ls(p) (p<<1)
        #define rs(p) (p<<1|1)
        struct node {
            int l, r;
            vector<fun> convex;
            int sum, val;
        } tr[MAXN<<2];
        void pushup(int p) {
            convex(p)=convex(ls(p));
            auto &now=convex(p);
            for (const auto &i: convex(rs(p))) {
                while (now.size()>1 && point(*next(rbegin(now)),i)<point(*next(rbegin(now)),*rbegin(now))) now.pop_back();
                now.push_back(i);
            }
            while (now.size()>1 && (*begin(now))(tot)<=(*next(begin(now)))(tot)) now.erase(now.begin());
            sum(p)=sum(ls(p))+sum(rs(p));
        }
        void build(int cl, int cr, int a[], int p=1) {
            ll(p)=cl; rr(p)=cr;
            if (cl==cr) {
                val(p)=sum(p)=a[cl];
                convex(p)={{cl,a[cl]}};
                return;
            }
            int mid=(cl+cr)>>1;
            build(cl,mid,a,ls(p)); build(mid+1,cr,a,rs(p));
            pushup(p);
        }
        void maintain(int l, int r, int v, int p=1) {
            int cl=ll(p), cr=rr(p);
            if (cl==cr) {
                val(p)=min(val(p)+cl*tot,v)-cl*tot;
                sum(p)=val(p);
                convex(p)={{cl,val(p)}};
                return;
            }
            int i=0;
            while (i+1<(int)convex(p).size() && convex(p)[i](tot)<convex(p)[i+1](tot)) ++i;
            if (convex(p)[i](tot)<=v) return;
            int mid=(cl+cr)>>1;
            if (l<=mid) maintain(l,r,v,ls(p));
            if (r>mid) maintain(l,r,v,rs(p));
            pushup(p);
        }
        int qsum(int l, int r, int p=1) {
            int cl=ll(p), cr=rr(p);
            if (l<=cl&&cr<=r) return sum(p);
            // if (cl==cr) return sum(p)+cl*tot;
            int mid=(cl+cr)>>1, res=0;
            if (l<=mid) res+=qsum(l,r,ls(p));
            if (r>mid) res+=qsum(l,r,rs(p));
            return res;
        }
    } sg;  
    void solve() {
        sg.build(1,n,a);
        for (const auto& [t,x,y]: q) {
            if (t==1) sg.maintain(1,n,x);
            else if (t==2) tot++;
            else cout<<sg.qsum(x,y)+(y-x+1)*(x+y)*tot/2<<'\n';
        }
    }
};

namespace solve_sub2 {
    void solve() {
        
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for (int i=1; i<=n; ++i) cin>>a[i];
    int has_2=0;
    for (int i=0,t,x,y; i<m; ++i) {
        cin>>t; x=y=0;
        has_2|=t==2;
        if (t==1) {
            cin>>x;
        } else if (t==3) {
            cin>>x>>y;
        }
        q.push_back({t,x,y});
    }
    // if (n<=5000 || has_2) 
    solve_sub1::solve();
    // else solve_sub2::solve();
}