#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int B=110;typedef long long ll;int n;int m;const ll minf=-(1LL<<47);//点结构体，叉积计算
struct poi{ll x;ll y;friend poi operator +(poi a,poi b){return (poi){a.x+b.x,a.y+b.y};}};
inline bool cmp(const poi& a,const poi& b,const poi& c){return (a.y-c.y)*(a.x-b.x)>=(a.y-b.y)*(a.x-c.x);}
inline bool cmp(const poi& a,const poi& b,const ll& k){return k*(b.x-a.x)>=b.y-a.y;}
inline bool cmp(const poi& a,const poi& b,const poi& c,const poi& d)
{return (c.y-d.y)*(a.x-b.x)>=(a.y-b.y)*(c.x-d.x);}
inline void chull(poi* st,int& tp)//jarvis水平步进法求凸包
{int i,r;for(i=2,r=tp,tp=1;i<=r;i++){while(tp>1&&cmp(st[tp-1],st[tp],st[i]))tp--;st[++tp]=st[i];}}
struct data//最大子段和的结构体
{
    ll sum;ll l;ll r;ll ans;
    friend data operator +(data a,data b)
    {return (data){a.sum+b.sum,max(a.sum+b.l,a.l),max(a.r+b.sum,b.r),max(a.r+b.l,max(a.ans,b.ans))};}
};poi st[B+10];ll asum[B+10];
inline void ins(const poi& a){st[a.x].y=max(st[a.x].y,a.y);}
struct block
{
    data val;int siz;poi pre[B+10];poi suf[B+10];poi ans[B+10];ll a[B+10];ll add;bool FLG;
    int p1;int p2;int p3;int s1;int s2;int s3;int cut;
    inline int brusolve(int l,int r)//暴力代码
    {
        ll sum=0;for(int i=l+1;i<=r;i++)sum+=a[i],ans[i]=(poi){i-l,sum};
        for(int i=l+2;i<=r;i++)
            {sum=0;poi* nw=ans+l+1;for(int j=i;j<=r;j++,++nw)sum+=a[j],nw->y=max(nw->y,sum);}
        s3=r-l;chull(ans+l,s3);return s3;
    }
    inline int solve(int l,int r)//暴力剪枝和单调性剪枝
    {
        if(r-l<cut)return 0;if(r-l<=16){return brusolve(l,r);}
        int mid=(l+r)/2;int t1=solve(l,mid);int t2=solve(mid,r);
        for(int i=1;i<=r-l;i++)st[i]=(poi){i,minf};//插入左右两边的凸包
        for(int i=l+1;i<=l+t1;i++)ins(ans[i]);for(int i=mid+1;i<=mid+t2;i++)ins(ans[i]);
        ll sum=0;s1=0;for(int i=mid+1;i<=r;i++)s1++,sum+=a[i],pre[s1]=(poi){s1,sum};chull(pre,s1);
           sum=0;s2=0;for(int i=mid;i>l;i--)s2++,sum+=a[i],suf[s2]=(poi){s2,sum};chull(suf,s2);
        int i=1;int j=1;ins(pre[i]+suf[j]);//闵可夫斯基和合并凸包
        while(i!=s1&&j!=s2)
        {(cmp(pre[i],pre[i+1],suf[j],suf[j+1])?j:i)++;ins(pre[i]+suf[j]);}
        if(i!=s1)for(i++;i<=s1;i++)ins(pre[i]+suf[j]);
        if(j!=s2)for(j++;j<=s2;j++)ins(pre[i]+suf[j]);
        chull(st,s3=r-l);for(int i=1;i<=s3;i++)ans[l+i]=st[i];return s3;
    }//暴力向右爬的函数
    inline void aju(poi* a,int& p,const int& t){while(p!=t)if(cmp(a[p],a[p+1],-add))break;else p++;}
    inline void rebuild()
    {
        for(int i=1;i<=siz;i++)a[i]+=add;add=0;//判一下是否全部爬到底
        if(FLG==false){FLG=true;for(int i=1;i<=siz;i++)FLG=FLG&&(a[i]>=0);}
        if(FLG){val.sum=0;for(int i=1;i<=siz;i++)val.sum+=a[i];val.l=val.r=val.ans=val.sum;return;}
        cut=ans[p3].x;solve(0,siz);
        ll sum=0;s1=0;for(int i=1;i<=siz;i++)s1++,sum+=a[i],pre[s1]=(poi){s1,sum};chull(pre,s1);
           sum=0;s2=0;for(int i=siz;i>=1;i--)s2++,sum+=a[i],suf[s2]=(poi){s2,sum};chull(suf,s2);
        p1=1;aju(pre,p1,s1);p2=1;aju(suf,p2,s2);p3=1;aju(ans,p3,s3);
        FLG&=(p1==s1)&&(p2==s2)&&(p3==s3);
        val=(data){sum,max(pre[p1].y,0LL),max(suf[p2].y,0LL),max(ans[p3].y,0LL)};
    }
    inline ll calc(const poi& a){return max(a.x*add+a.y,0LL);}
    inline void lb_add(ll x)
    {
        if(FLG){add+=x;val.sum+=siz*x;val.l=val.r=val.ans=val.sum;return;}
        add+=x;aju(pre,p1,s1);aju(suf,p2,s2);aju(ans,p3,s3);
        FLG&=(p1==s1)&&(p2==s2)&&(p3==s3);//暴力向右爬一下
        val=(data){val.sum+siz*x,calc(pre[p1]),calc(suf[p2]),calc(ans[p3])};
    }
    inline data calc(int l,int r)
    {
        data ret=(data){0,0,0,0};
        int tp=0;for(int i=l;i<=r;i++)asum[++tp]=a[i]+add;
        for(int i=1;i<=tp;i++)ret.sum+=asum[i],ret.l=max(ret.l,ret.sum);ret.sum=0;
        for(int i=tp;i>=1;i--)ret.sum+=asum[i],ret.r=max(ret.r,ret.sum);ll mi=0;
        for(int i=1;i<=tp;i++)asum[i]+=asum[i-1];
        for(int i=1;i<=tp;i++)ret.ans=max(ret.ans,asum[i]-mi),mi=min(mi,asum[i]);
        return ret;
    }
    inline ll fstcalc(int l,int r)//如果是同一个块直接暴力就行了
    {
        int tp=0;for(int i=l;i<=r;i++)asum[++tp]=a[i]+add;
        for(int i=1;i<=tp;i++)asum[i]+=asum[i-1];ll mi=0;ll ans=0;
        for(int i=1;i<=tp;i++)ans=max(ans,asum[i]-mi),mi=min(mi,asum[i]);return ans;
    }
}bl[(N/B)+10];int bi[N];int bj[N];
int main()
{
    scanf("%d%d",&n,&m);//分块的一般操作
    for(int i=0,t=1;i<n;i+=B,t++)
    {
        for(int j=1;j<=B&&i+j<=n;j++)scanf("%lld",&bl[t].a[j]),bi[i+j]=t,bj[i+j]=j;
        bl[t].siz=min(n-i,B);bl[t].rebuild();
    }
    for(int i=1;i<=m;i++)
    {
        int t;int l;int r;ll x;scanf("%d%d%d",&t,&l,&r);
        if(t==1)
        {
            scanf("%lld",&x);
            if(bi[l]==bi[r]){for(int i=bj[l];i<=bj[r];i++)bl[bi[l]].a[i]+=x;bl[bi[l]].rebuild();}
            else
            {
                for(int i=bj[l];i<=B;i++)bl[bi[l]].a[i]+=x;bl[bi[l]].rebuild();
                for(int i=bi[l]+1;i<bi[r];i++)bl[i].lb_add(x);
                for(int i=1;i<=bj[r];i++)bl[bi[r]].a[i]+=x;bl[bi[r]].rebuild();
            }
        }
        else
        {
            if(bi[l]==bi[r]){printf("%lld\n",bl[bi[l]].fstcalc(bj[l],bj[r]));}
            else
            {
                data ret=bl[bi[l]].calc(bj[l],B);
                for(int i=bi[l]+1;i<bi[r];i++)ret=ret+bl[i].val;
                ret=ret+bl[bi[r]].calc(1,bj[r]);printf("%lld\n",ret.ans);
            }
        }
    }return 0;
}