//integer may be negative,so Read() should be noticed
max(a,b){return a>b?a:b;}
#define mid l+(r-l>>1)
#define lc h<<1
#define rc h<<1|1
#define IN x<=l&&r<=y//important
tr[4000001],lzy1[4000001],lzy2[4000001];
void Pushup(h){tr[h]=max(tr[lc],tr[rc]);}
void Pushdown(h){
  if(lzy1[h]){
    lzy1[lc]=lzy1[rc]=lzy1[h],lzy2[lc]=lzy2[rc]=lzy2[h];
    tr[lc]=tr[rc]=lzy1[h]+lzy2[h];
  }
  else if(lzy2[h]){
    lzy2[lc]+=lzy2[h],lzy2[rc]+=lzy2[h];
    tr[lc]+=lzy2[h],tr[rc]+=lzy2[h];
  }
  lzy1[h]=lzy2[h]=0;
}
void Build(h,l,r){
  //printf("Build:[h=%d,l=%d,r=%d]\n",h,l,r);
  if(l==r){scanf("%d",tr+h);return;}
  Build(lc,l,mid),Build(rc,mid+1,r);
  Pushup(h);
}
Query(h,l,r,x,y){
  //printf("Query:[h=%d,l=%d,r=%d,x=%d,y=%d]\n",h,l,r,x,y);
  if(IN)return tr[h];
  Pushdown(h);
  if(y<=mid)return Query(lc,l,mid,x,y);
  if(x>mid)return Query(rc,mid+1,r,x,y);
  return max(Query(lc,l,mid,x,y),Query(rc,mid+1,r,x,y));
}
void Modify(h,l,r,x,y,k){
  //printf("Modify:[h=%d,l=%d,r=%d,x=%d,y=%d,k=%d]\n",h,l,r,x,y,k);
  if(IN){tr[h]=k;lzy1[h]=k,lzy2[h]=0;return;}
  Pushdown(h);
      if(y<=mid)Modify(lc,l,mid,x,y,k);
  else if(x>mid)Modify(rc,mid+1,r,x,y,k);
  else Modify(lc,l,mid,x,y,k),Modify(rc,mid+1,r,x,y,k);
  Pushup(h);
}                            
void Update(h,l,r,x,y,k){
  //printf("Update:[h=%d,l=%d,r=%d,x=%d,y=%d,k=%d]\n",h,l,r,x,y,k);
  if(IN){tr[h]+=k;lzy2[h]+=k;return;}
  Pushdown(h);
      if(y<=mid)Update(lc,l,mid,x,y,k);
  else if(x>mid)Update(rc,mid+1,r,x,y,k);
  else Update(lc,l,mid,x,y,k),Update(rc,mid+1,r,x,y,k);
  Pushup(h);
}
main(){
  int n,q;scanf("%d%d",&n,&q);
  Build(1,1,n);
  while(q--){
    int op,x,y;scanf("%d%d%d",&op,&x,&y);
         if(op==1){int z;scanf("%d",&z);Modify(1,1,n,x,y,z);}
    else if(op==2){int z;scanf("%d",&z);Update(1,1,n,x,y,z);}
    else if(op==3)printf("%d\n",Query(1,1,n,x,y));
  }
}