1 #include<bits/stdc++.h>

  2 using namespace std;

  3 const int N=1e6+10;

  4 typedef long long ll;

  5 struct node{

  6     ll mmax,l,r;

  7     ll tag1,tag2;//修改，加

  8 }t[N<<2];

  9 ll n,q,a[N];

 10

 11 void up(ll k){

 12     t[k].mmax=max(t[k<<1].mmax,t[k<<1|1].mmax);

 13 }

 14

 15 void rev(ll k,ll x,ll y){

 16     if(x==1e9+1){

 17         t[k].tag2+=y;

 18         t[k].mmax+=y;

 19     }

 20     else{

 21         t[k].tag1=x;

 22         t[k].tag2=y;

 23         t[k].mmax=x+y;

 24     }

 25 }

 26

 27 void pd(ll k){

 28     rev(k<<1,t[k].tag1,t[k].tag2);

 29     rev(k<<1|1,t[k].tag1,t[k].tag2);

 30     t[k].tag1=1e9+1;

 31     t[k].tag2=0;

 32 }

 33

 34 /*void downtag1(ll k){

 35     if(t[k].tag1!=1e9+1){

 36         t[k<<1].mmax=t[k<<1].tag1=t[k].tag1;

 37         t[k<<1].tag2=0;

 38         t[k<<1|1].mmax=t[k<<1|1].tag1=t[k].tag1;

 39         t[k<<1|1].tag2=0;

 40         t[k].tag1=1e9+1;

 41     }

 42 }

 43

 44 void downtag2(ll k){

 45     t[k<<1].tag2+=t[k].tag2;

 46     t[k<<1].mmax+=t[k].tag2;

 47     t[k<<1|1].tag2+=t[k].tag2;

 48     t[k<<1|1].mmax+=t[k].tag2;

 49     t[k].tag2=0;

 50 }*/

 51

 52 void build(ll k,ll l,ll r){

 53     t[k].l=l,t[k].r=r,t[k].tag1=1e9+1;

 54     if(l==r){

 55         t[k].mmax=a[l];

 56         return ;

 57     }

 58     ll mid=(l+r)>>1;

 59     build(k<<1,l,mid);build(k<<1|1,mid+1,r);

 60     up(k);

 61 }

 62

 63 void change1(ll k,ll l,ll r,ll x){

 64     if(t[k].l>=l && t[k].r<=r){

 65         t[k].mmax=x;

 66         t[k].tag1=x,t[k].tag2=0;

 67         return ;

 68     }

 69     pd(k);

 70     //downtag1(k),downtag2(k);

 71     ll mid=(t[k].l+t[k].r)>>1;

 72     if(l<=mid) change1(k<<1,l,r,x);

 73     if(r>mid) change1(k<<1|1,l,r,x);

 74     up(k);

 75 }

 76

 77 void change2(ll k,ll l,ll r,ll x){

 78     if(t[k].l>=l && t[k].r<=r){

 79         t[k].mmax+=x;

 80         t[k].tag2+=x;

 81         return ;

 82     }

 83     pd(k);

 84     //downtag1(k),downtag2(k);

 85     ll mid=(t[k].l+t[k].r)>>1;

 86     if(l<=mid) change2(k<<1,l,r,x);

 87     if(r>mid) change2(k<<1|1,l,r,x);

 88     up(k);

 89 }

 90

 91 ll query(ll k,ll l,ll r){

 92     if(t[k].l>=l && t[k].r<=r) return t[k].mmax;

 93     pd(k);

 94     //downtag1(k),downtag2(k);

 95     ll mid=(t[k].l+t[k].r)>>1;

 96     ll ans=-1e18;

 97     if(l<=mid) ans=max(ans,query(k<<1,l,r));

 98     if(r>mid) ans=max(ans,query(k<<1|1,l,r));

 99     return ans;

100 }

101

102 int main(){

103     scanf("%lld%lld",&n,&q);

104     for(int i=1;i<=n;i++)

105         scanf("%lld",&a[i]);

106     build(1,1,n);

107     while(q--){

108         ll op,l,r,x;

109         scanf("%lld%lld%lld",&op,&l,&r);

110         if(op==1){

111             scanf("%lld",&x);

112             change1(1,l,r,x);

113         }

114         else if(op==2){

115             scanf("%lld",&x);

116             change2(1,l,r,x);

117         }

118         else cout<<query(1,l,r)<<endl;

119     }

120 }