#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstring>

#define int long long
#define mkp std::make_pair


namespace IO{
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char tmp[BUFSIZE];int cnt=0;
	inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
	int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	
	void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
	void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
	void putint(int x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	
	struct Basic{
		Basic &operator>>(int &A){A=IO::readInt();return (*this);}

		Basic &operator<<(const int &A){putint(A);return (*this);}

		void Flush(){flush();}
	}lin,lout;
}

const int N=1e5+5;
const int B=800;

auto gc=getchar_unlocked;
int rd(){
    int res=0,op=1; char c=gc();
    while((c>'9'||c<'0')&&c!='-') c=gc();
    if(c=='-') op=-1,c=gc();
    while((c<='9')&&(c>='0')) res=res*10+c-'0', c=gc();
    return res*op;
}

using pii=std::pair<int,int>;

struct Query{
    int o,x,y,z;
};
struct Node{
    int ls,rs,s;
    int sm;
    __inline friend Node operator+(const Node& a,const Node& b){
        return (Node){std::max(a.ls,b.ls+a.sm),std::max(a.rs+b.sm,b.rs),std::max(std::max(a.s,b.s),a.rs+b.ls),a.sm+b.sm};
    }
};

clock_t Tbg,Ted;
double Tres=0;

int n,m;
int a[N+5];
Query qu[N];
int dlt[N];
const int K=256,R=4,I=8;
const int V=255;
int li[N],cnt[K],L;
int CMK=0,CMX=0;
Node ans[N];

namespace blk{
    int b[B+5];
    int tg=0;
    int bl,br;
    int sm=0;
}

namespace conv{
    using ll=long long;
    using Conv=std::vector<pii>;
    void mink(Conv p,Conv q,Conv &res){
        res.clear();
        int ps=p.size(),qs=q.size();
        for(int i=ps-1;i>=1;i--) p[i].first-=p[i-1].first,p[i].second-=p[i-1].second;
        for(int i=qs-1;i>=1;i--) q[i].first-=q[i-1].first,q[i].second-=q[i-1].second;
        int x=0,y=0,sz=ps+qs;
        for(int i=0;i<sz;i++){
            if(x>=ps) res.emplace_back(q[y++]);
            else if(y>=qs) res.emplace_back(p[x++]);
            else if((ll)p[x].first*q[y].second>(ll)q[y].first*p[x].second){
                res.emplace_back(q[y++]);
            }else res.emplace_back(p[x++]);
        }
        for(int i=1;i<sz;i++)
            res[i].first+=res[i-1].first,res[i].second+=res[i-1].second;
    }
    inline void mix(Conv &p,Conv &q,Conv &res){
        res.clear(); // res.push_back(std::make_pair(0,0));
        int ps=p.size(),qs=q.size();
        int sz=ps+qs,x=0,y=0;
        for(int i=0;i<sz;i++){
            pii *np;
            if(x>=ps) np=&q[y++];
            else if(y>=qs) np=&p[x++];
            else if(p[x]<q[y]) np=&p[x++];
            else np=&q[y++];
            if((!res.empty())&&(*np).first==res.back().first){
                res.pop_back();
            }        
            while(res.size()>=2){
                int sz=res.size();
                if((res[sz-1].second-res[sz-2].second)*(np->first-res[sz-1].first)>
                    (np->second-res[sz-1].second)*(res[sz-1].first-res[sz-2].first))
                    break;
                res.pop_back();
            }
            if(res.size()==1&&res[0].second*((*np).first-res[0].first)<
               ((*np).second-res[0].second)*res[0].first) res.pop_back();
            res.emplace_back(*np);
        }
        return;
    }
    inline void nmix(const Conv &p,const Conv &q,Conv &res){
        int ps=p.size(),qs=q.size();
        res=p;
        int sz=q.size();
        for(int i=0;i<sz;i++){
            while(res.size()>=2){
                int sz=res.size();
                if((res[sz-1].second-res[sz-2].second)*(q[i].first-res[sz-1].first)>
                    (q[i].second-res[sz-1].second)*(res[sz-1].first-res[sz-2].first))
                    break;
                res.pop_back();
            }
            if(res.size()==1&&res[0].second*(q[i].first-res[0].first)<
               (q[i].second-res[0].second)*res[0].first) res.pop_back();
            res.emplace_back(q[i]);
        }
        return;
    }
    void mv(Conv &cv,const int d){
        int sz=cv.size(); for(int i=0;i<sz;i++) cv[i].second+=cv[i].first*d;
        return;
    }
    inline void mv(Conv &cv,const int u,const int r){
        int sz=cv.size();
        for(int i=0;i<sz;i++) cv[i].first+=r,cv[i].second+=u;
        return;
    }
}
namespace sgt{
    conv::Conv lcv[(B+5)<<2],rcv[(B+5)<<2],scv[(B+5)<<2];
    int tg[(B+5)<<2],s[(B+5)<<2],len[(B+5)<<2];
    inline int ls(int id){
        return (id<<1);
    }
    inline int rs(int id){
        return ((id<<1)|1);
    }
    void dotag(int id,int tgv){
        conv::mv(scv[id],tgv),conv::mv(lcv[id],tgv),conv::mv(rcv[id],tgv);
        s[id]+=len[id]*tgv;
    }

    void update(int id){
        // Tbg=clock();
        s[id]=s[ls(id)]+s[rs(id)];
        conv::Conv tmp;
        tmp=rcv[ls(id)];
        conv::mv(tmp,s[rs(id)],len[rs(id)]); conv::nmix(rcv[rs(id)],tmp,rcv[id]);
        tmp=lcv[rs(id)];
        conv::mv(tmp,s[ls(id)],len[ls(id)]); conv::nmix(lcv[ls(id)],tmp,lcv[id]);
        conv::mink(rcv[ls(id)],lcv[rs(id)],scv[id]);
        conv::mix(scv[ls(id)],scv[id],tmp);
        conv::mix(scv[rs(id)],tmp,scv[id]);
        dotag(id,tg[id]);
        // Ted=clock();
        // Tres+=(Ted-Tbg)*1.0;
        
        return;
    }
    void build(int id,int l,int r){
        len[id]=r-l+1,tg[id]=0;
        if(l==r){
            s[id]=blk::b[l];
            lcv[id].clear(),rcv[id].clear(),scv[id].clear();
            lcv[id].emplace_back(mkp(1,blk::b[l]));    
            rcv[id].emplace_back(mkp(1,blk::b[l]));
            scv[id].emplace_back(mkp(1,blk::b[l]));
            return;
        }
        int mid=(l+r)>>1;
        build(ls(id),l,mid),build(rs(id),mid+1,r);
        update(id);
        
        return;
    }
    void change(int id,int l,int r,int tl,int tr,int val){
        if(tl<=l&&r<=tr){
            tg[id]+=val; dotag(id,val);
            return;
        }
        int mid=(l+r)>>1;
        if(!(tl>mid)) change(ls(id),l,mid,tl,tr,val);
        if(!(tr<=mid)) change(rs(id),mid+1,r,tl,tr,val);
        update(id);
        return;
    }
}

namespace srt{
    int tmp[N];
    void usrsrt(){
#ifdef TEST
        for(int i=1;i<=L;i++) li[i]>>=32;
        return;
#endif
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=L;i++) cnt[li[i]&V]++;
        for(int i=1;i<=V;i++){
            cnt[i]+=cnt[i-1];
        }
        for(int i=L;i>=1;i--){
            tmp[cnt[li[i]&V]--]=li[i];
        }
        for(int i=1;i<=L;i++) li[i]=tmp[i]>>I;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=L;i++) cnt[li[i]&V]++;
        for(int i=1;i<=V;i++){
            cnt[i]+=cnt[i-1];
        }
        for(int i=L;i>=1;i--){
            tmp[cnt[li[i]&V]--]=li[i];
        }
        for(int i=1;i<=L;i++) li[i]=tmp[i]>>I;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=L;i++) cnt[li[i]&V]++;
        for(int i=1;i<=V;i++){
            cnt[i]+=cnt[i-1];
        }
        for(int i=L;i>=1;i--){
            tmp[cnt[li[i]&V]--]=li[i];
        }
        for(int i=1;i<=L;i++) li[i]=tmp[i]>>I;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=L;i++) cnt[li[i]&V]++;
        for(int i=1;i<=V;i++){
            cnt[i]+=cnt[i-1];
        }
        for(int i=L;i>=1;i--){
            tmp[cnt[li[i]&V]--]=li[i];
        }
        for(int i=1;i<=L;i++) li[i]=tmp[i]>>I;
        return;
    }
    inline void stdsrt(){
        std::sort(li+1,li+L+1,[](int& x,int& y){
            return (x&0xffffffff)<(y&0xffffffff);
        });
        for(int i=1;i<=L;i++) li[i]>>=32;
        return;
    }
    const int B=1200;
    void sort(){
        if(L<=B) stdsrt();
        else usrsrt();
        return;
    }
}

namespace blk{
    int ps=0,pl=0,pr=0;
    __inline void sadd(int l,int r,int val){
        sm+=(r-l+1)*val;
        for(int i=1;i<=B;i++) b[i]+=tg+val*(l<=i&&i<=r);
        tg=0;
        return; 
    }
    __inline void badd(int val){
        tg+=val; sm+=val*B;
        return;
    }
    int qsm(int l,int r){
        int res=0; for(int i=l;i<=r;i++) res+=b[i];
        res+=(r-l+1)*tg;  
        return res;
    }
    int qsm(){
        return sm;
    }
    Node calc(int l,int r){
        for(int i=1;i<=B;i++) b[i]+=tg; tg=0;
        Node res; res.sm=qsm(l,r);
        int x=0;
        x=0; res.ls=0; for(int i=l;i<=r;i++) x+=b[i],res.ls=std::max(res.ls,x);
        x=0; res.rs=0; for(int i=r;i>=l;i--) x+=b[i],res.rs=std::max(res.rs,x);
        x=0; res.s=0;
        for(int i=l;i<=r;i++) x=std::max(x+b[i],0ll),res.s=std::max(res.s,x);
        return res;
    }
    __inline void build(){
        sgt::build(1,1,B);
        sm=0;
        for(int i=1;i<=B;i++) sm+=b[i];
        tg=0;
        return;
    }
    void sv(int l,int r){
        int mx=-1e12;
        for(int i=1;i<=B;i++) b[i]+=tg,mx=std::max(mx,b[i]);
        tg=0;
        int cnt=0; L=0;
        int hav=0;
        for(int i=l;i<=r;i++){
            if(qu[i].o==1){
                if(qu[i].y<bl||qu[i].x>br){
                    hav=0;
                    continue;
                }
                cnt+=qu[i].z; hav=0;
            }else{
                if(qu[i].x<=bl&&br<=qu[i].y){
                    if(cnt+mx<=0){
                        Node nn;
                        nn.ls=0,nn.rs=0;
                        nn.s=0; nn.sm=sm+cnt*B;
                        ans[i]=ans[i]+nn;
                        hav=0;
                        continue;
                    }
                    if(hav) continue;
                    hav=1;
                    dlt[i]=cnt;
                    li[++L]=(i<<35)+cnt+(1ll<<31);
                }else hav=0;
            }
        }
        if(L){
            srt::sort();
            ps=0,pl=0,pr=0;
            conv::Conv *cvs=&sgt::scv[1],*cvl=&sgt::lcv[1],*cvr=&sgt::rcv[1];
            int ssz=(*cvs).size(),lsz=(*cvl).size(),rsz=(*cvr).size();
            for(int i=1;i<=L;i++){
                int id=li[i]>>3;
                while(ps+1<ssz){
                    if(dlt[id]*((*cvs)[ps+1].first-(*cvs)[ps].first)+
                        ((*cvs)[ps+1].second-(*cvs)[ps].second)<0) break;
                    ++ps;
                }
                while(pl+1<lsz){
                    if(dlt[id]*((*cvl)[pl+1].first-(*cvl)[pl].first)+
                        ((*cvl)[pl+1].second-(*cvl)[pl].second)<0) break;
                    ++pl;
                }
                while(pr+1<rsz){
                    if(dlt[id]*((*cvr)[pr+1].first-(*cvr)[pr].first)+
                        ((*cvr)[pr+1].second-(*cvr)[pr].second)<0) break;
                    ++pr;
                }
                Node nn;
                nn.ls=std::max((*cvl)[pl].first*dlt[id]+(*cvl)[pl].second,0ll);
                nn.rs=std::max((*cvr)[pr].first*dlt[id]+(*cvr)[pr].second,0ll);
                nn.s=std::max((*cvs)[ps].first*dlt[id]+(*cvs)[ps].second,0ll);
                nn.sm=B*dlt[id]+sm;
                for(int j=id;j<=r;j++){
                    if(qu[j].o==1){
                        if(qu[j].y<bl||qu[j].x>br) break;
                        break;
                    }else if(qu[j].x<=bl&&qu[j].y>=br){
                        ans[j]=ans[j]+nn;
                    }else break;
                }
            }
        }
        cnt=0;
        for(int i=l;i<=r;i++){
            if(qu[i].o==1){
                if(qu[i].y<bl||qu[i].x>br) continue;
                badd(qu[i].z);
                cnt+=qu[i].z;
            }else if(qu[i].o==2){
                if(qu[i].y<bl||qu[i].x>br) continue;
                if(qu[i].x<=bl&&br<=qu[i].y) continue;
                int tl=std::max(qu[i].x,bl)-bl+1,tr=std::min(qu[i].y,br)-bl+1;
                if(mx+cnt>0) ans[i]=ans[i]+calc(tl,tr);
                else{
                    Node nn;
                    nn.ls=0,nn.rs=0;
                    nn.s=0,nn.sm=qsm(tl,tr);
                    ans[i]=ans[i]+nn;
                }
            }
        }

        sgt::change(1,1,B,1,B,cnt);

        return;
    }
    bool chk(int i){
        if(qu[i].x<=bl&&br<=qu[i].y){
            return false;
        }else if(qu[i].x>br||qu[i].y<bl){
            return false;
        }else{
            return true;
        }
    }
    void sv(){
        build();
        for(int i=1;i<=m;i++){
            for(int j=i;j<=m;j++){
                if(qu[j].o==1) if(chk(j)){
                    if(i!=j){
                        sv(i,j-1);
                    }
                    int tl=std::max(qu[j].x,bl)-bl+1,tr=std::min(qu[j].y,br)-bl+1;
                    sadd(tl,tr,qu[j].z); sgt::change(1,1,B,tl,tr,qu[j].z);
                    i=j;
                    break;
                }
                if(j==m) sv(i,m),i=m;
            }
        }

        return;
    }
}

signed main(){
    n=IO::readInt(),m=IO::readInt();
    for(int i=1;i<=n;i++) a[i]=IO::readInt();
    for(int i=1;i<=m;i++){
        qu[i].o=IO::readInt(),qu[i].x=IO::readInt(),qu[i].y=IO::readInt();
        if(qu[i].o&1) qu[i].z=IO::readInt();
    }
    for(int i=1;i<=n;i+=B){
        for(int j=1;j<=B;j++){
            if(i+j-1<=n) blk::b[j]=a[i+j-1];
            else blk::b[j]=0;
        }
        blk::bl=i,blk::br=i+B-1;
        blk::sv();
    }
    for(int i=1;i<=m;i++){
        if(qu[i].o&2){
            IO::putint(ans[i].s),IO::putch('\n');
        }
    }
    IO::flush();
    return 0;
}