T148T1

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;

struct Node{
    ll mx[8];
    ll tag;

    inline void operator += (const ll &x){
        for(int i=0;i<8;++i)mx[i]+=x;
        tag+=x;
    }

    inline Node operator +(const Node &x){
        Node ret;
        for(int i=0;i<8;++i){
            ret.mx[i]=max(mx[i],x.mx[i]);
        }
        ret.tag=0;
        return ret;
    }
}tr[N<<2];

ll sum;
ll A[N];

inline void init(Node &x,int p){
    ll a=A[p];
    ll b=A[p+1];
    ll c=A[p+2];
    ll tmp=sum-abs(a)-abs(b)-abs(c);
    x.mx[0]=tmp+a+b+c;
    x.mx[1]=tmp-a+b+c;
    x.mx[2]=tmp+a-b+c;
    x.mx[3]=tmp+a+b-c;
    x.mx[4]=tmp-a-b+c;
    x.mx[5]=tmp-a+b-c;
    x.mx[6]=tmp+a-b-c;
    x.mx[7]=tmp-a-b-c;
}

#define ls (rt<<1)
#define rs (rt<<1|1)

inline void update(int rt){
    tr[rt]=tr[ls]+tr[rs];
}

void build(int rt,int l,int r){
    if(l==r)return init(tr[rt],l);
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    update(rt);
}

inline void pushdown(int rt){
    if(tr[rt].tag){
        tr[ls]+=tr[rt].tag;
        tr[rs]+=tr[rt].tag;
        tr[rt].tag=0;
    }
}

void change(int rt,int l,int r,int x,int y){
    if(l==r)return init(tr[rt],l);
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid)change(ls,l,mid,x,y);
    if(y>mid)change(rs,mid+1,r,x,y);
    update(rt);
}

Node query(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[rt];
    pushdown(rt);
    int mid=(l+r)>>1;
    if(y<=mid)return query(ls,l,mid,x,y);
    if(x>mid)return query(rs,mid+1,r,x,y);
    return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
}

int n,m;

inline void Change(int l,int r){
    l=max(1,l);
    r=min(r,n);
    if(l<=r)change(1,1,n,l,r);
}

inline ll Query(int l,int r,ll v){
    Node t=query(1,1,n,l,r);
    ll ans=0;
    ans=max(ans,t.mx[0]+3*v);
    ans=max(ans,t.mx[1]+1*v);
    ans=max(ans,t.mx[2]+1*v);
    ans=max(ans,t.mx[3]+1*v);
    ans=max(ans,t.mx[4]-1*v);
    ans=max(ans,t.mx[5]-1*v);
    ans=max(ans,t.mx[6]-1*v);
    ans=max(ans,t.mx[7]-3*v);
    return ans;
}

int main(){
    freopen("pipi.in","r",stdin);
    freopen("pipi.out","w",stdout);
    r(n),r(m);
    for(int i=1;i<=n;++i)r(A[i]);
    for(int i=1;i<=n;++i){
        sum+=abs(A[i]);
    }
    n-=2;
    build(1,1,n);
    while(m--){
        int opt;r(opt);
        if(opt==1){
            int pos,v;r(pos),r(v);
            int delta=abs(v)-abs(A[pos]);
            tr[1]+=delta;
            sum+=delta;
            A[pos]=v;
            Change(pos-2,pos);
        }
        else {
            int l,r,u;
            r(l),r(r),r(u);
            printf("%lld\n",Query(l,r-2,u));
        }
    }
    return 0;
}