#include <bits/stdc++.h>
#define For(i,s,e) for(int i=s;i<=e;i++)
#define dFor(i,s,e) for(int i=s;i>=e;i--)
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
const int MaxN=1145141;
int n,q,a[MaxN],ans[4][MaxN<<2];
void push_up(int p){//0->l 1->r
	ans[2][p]=ans[2][ls]+ans[2][rs];
	ans[0][p]=max(ans[0][ls],ans[2][ls]+ans[0][rs]);
	ans[1][p]=max(ans[1][rs],ans[2][rs]+ans[1][ls]);
	ans[3][p]=max(max(ans[3][ls],ans[3][rs]),ans[1][ls]+ans[0][rs]);
}
void build(int p,int l,int r){
	if(l==r){
		ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(p);
}
void update(int n,int p,int k,int l,int r){
	if(n==l && n==r){
		ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(n<=mid)update(n,ls,k,l,mid);
	if(n>mid)update(n,rs,k,mid+1,r);
	push_up(p);
}
int query(int nl,int nr,int l,int r,int p){
	if(nl<=l && r<=nr)
		return ans[3][p];
	int res=-LLONG_MAX;
	int mid=(l+r)>>1;
	if(nl<=mid)res=max(res,query(nl,nr,l,mid,ls));
	if(nr>mid)res=max(res,query(nl,nr,mid+1,r,rs));
	return res;
}
signed main(){
    scanf("%lld%lld",&n,&q);
    For(i,1,n)scanf("%lld",a+i);
    build(1,1,n);
    while(q--){
    	int op,a,b;
    	scanf("%lld%lld%lld",&op,&a,&b);
		if(op==2){
			update(a,1,b,1,n);
		}else if(op==1){
			if(b<a)swap(a,b);
			printf("%lld\n",query(a,b,1,n,1));
		}else{// \/调试代码不用看
			For(o,0,3){
			int i=1,j=1,e=1;
            while(1){
                if(e>(n<<1))break;
                for(j=1;j<=1<<(i-1);j++){cout<<ans[o][e++]<<" ";}
                cout<<endl;
                i++;
            }}
		}
	}
    return 0;
}
/*
5 114
1
2
-3
4
5
*/