#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long a[N],ma[4*N],add[4*N],n,t;
void build(long long k,long long l,long long r){
	if(l==r){
		ma[k]=a[l];
		return;
	}
	long long mid=(l+r)>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	ma[k]=max(ma[k*2],ma[k*2+1]);
}
void change(long long k,long long l,long long r,long long x,long long y,long long v){
	if(x<=l&&r<=y&&l==r){
		ma[k]=v;
		return;
	}
	long long mid=(l+r)>>1;
	if(x<=mid)change(k*2,l,mid,x,y,v);
	if(y>mid)change(k*2+1,mid+1,r,x,y,v);
	ma[k]=max(ma[k*2],ma[k*2+1]);
}
long long query(long long k,long long l,long long r,long long x,long long y){
	if(x<=l&&r<=y)return ma[k];
	long long mid=(l+r)>>1,ans=0;
	if(x<=mid)ans=query(k*2,l,mid,x,y);
	if(y>mid)ans=max(ans,query(k*2+1,mid+1,r,x,y));
	return ans;
}
void update(long long k,long long l,long long r,long long x,long long y,long long v){
	if(x<=l&&r<=y){
		ma[k]+=v;
		return;
	}
	long long mid=(l+r)>>1;
	if(x<=mid)update(k*2,l,mid,x,y,v);
	if(y>mid)update(k*2+1,mid+1,r,x,y,v);
	ma[k]=max(ma[k*2],ma[k*2+1]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>t;
	for(long long i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(t--){
		long long x,k,p,v;
		cin>>x>>k>>p;
		if(x==1){
			cin>>v;
			change(1,1,n,k,p,v);
		}else if(x==2){
			cin>>v;
			update(1,1,n,k,p,v);
		}else cout<<query(1,1,n,k,p)<<"\n";
	}
	return 0;
}