#include<bits/stdc++.h>
using namespace std;
namespace IO{
    static char buf[1<<25],*p1,*p2;
    #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<25,stdin),p1==p2)?EOF:*p1++
	template<typename type>
	inline void read(type &x){
		x=0;int f=1;char ch=getchar();
		while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
		while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		x*=f;
	}
	template<typename type>
	inline void write(type x){
		x<0?x=-x,putchar('-'):0;
		static short sta[45],top=0;
		do sta[++top]=x%10,x/=10;while(x);
		while(top)putchar(sta[top--]|48);
	}
	template<typename type,typename ...T>
	inline void read(type&x,T&...y){read(x),read(y...);}
	template<typename type,typename ...T>
	inline void write(type x,T ...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
}
using namespace IO;
#define N 500005
typedef __int128 ll;
int n,m,a[N];
struct seg{
    int l,r;
    ll mx,sum,ans,t1,t2;
}s[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
ll query(int u,ll x){
    if(s[u].l==s[u].r)return max(x,s[u].mx);
    if(s[ls].mx>x)return query(ls,x)+s[u].sum-s[ls].sum;
    return x*(s[ls].r-s[ls].l+1)+query(rs,x);
}
void pushup(int u){
    s[u].mx=max(s[ls].mx,s[rs].mx);
    s[u].ans=s[ls].ans+s[rs].ans;
    s[u].sum=s[ls].sum+query(rs,s[ls].mx);
}
void put(int u,ll k){s[u].ans+=k*(s[u].r-s[u].l+1);s[u].t1+=k;}
void put(int u,ll t,ll k){
    if(s[u].l==s[u].r){s[u].ans+=max(s[u].mx,k)*t;return;}
    if(s[ls].mx>k){
        s[u].ans+=(query(ls,k)+s[u].sum-s[ls].sum)*t;
        put(ls,t,k);
        s[rs].t2+=t;
        s[rs].ans+=(s[u].sum-s[ls].sum)*t;
    }else{
        s[u].ans+=((s[ls].r-s[ls].l+1)*k+query(rs,k))*t;
        put(ls,k*t);
        put(rs,t,k);
    }
}
void pushdown(int u){
    put(ls,s[u].t1);put(rs,s[u].t1);
    if(s[u].t2){
        put(ls,s[u].t2,s[u^1].mx);
        put(rs,s[u].t2,max(s[ls].mx,s[u^1].mx));
    }
    s[u].t1=s[u].t2=0;
}
void build(int u,int l,int r){
    s[u].l=l;s[u].r=r;if(l==r){s[u].mx=s[u].sum=a[l];return;}
    int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);
}
ll qry(int u,int l,int r){
    if(s[u].l>r||s[u].r<l)return 0;
    if(s[u].l>=l&&s[u].r<=r)return s[u].mx;
    pushdown(u);return max(qry(ls,l,r),qry(rs,l,r));//notice pushdown needless
}
ll query(int u,int l,int r){
    if(s[u].l>r||s[u].r<l)return 0;
    if(s[u].l>=l&&s[u].r<=r)return s[u].ans;
    pushdown(u);return query(ls,l,r)+query(rs,l,r);
}
void update(int u,int x,ll k){
    if(s[u].l==s[u].r){s[u].mx=s[u].sum=k;return;}
    pushdown(u);x<=s[ls].r?update(ls,x,k):update(rs,x,k);pushup(u);
}
void update(int u,int l,int r,ll k){
    if(s[u].l>r||s[u].r<l)return;
    if(s[u].l>=l&&s[u].r<=r){put(u,1,k);return;}
    pushdown(u);update(ls,l,r,k);update(rs,l,r,max(k,qry(ls,l,r)));pushup(u);
}
int main(){
    int opt,x,y;
    read(n,m);
    for(int i=1;i<=n;++i)read(a[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i){
        read(opt,x,y);
        if(opt==1)update(1,x,y);
        else if(opt==2)update(1,x,y,0);
        else write(query(1,x,y)),putchar('\n');
    }
    return 0;
}#include<bits/stdc++.h>
using namespace std;
#define N 500005
typedef long long ll;
int n,m,a[N];
struct seg{
    int l,r;
    ll mx,sum,ans,t1,t2;
}s[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
ll query(int u,ll x){
    if(s[u].l==s[u].r)return max(x,s[u].mx);
    if(s[ls].mx>x)return query(ls,x)+s[u].sum-s[ls].sum;
    return x*(s[ls].r-s[ls].l+1)+query(rs,x);
}
void pushup(int u){
    s[u].mx=max(s[ls].mx,s[rs].mx);
    s[u].ans=s[ls].ans+s[rs].ans;
    s[u].sum=s[ls].sum+query(rs,s[ls].mx);
}
void put(int u,ll k){s[u].ans+=k*(s[u].r-s[u].l+1);s[u].t1+=k;}
void put(int u,ll t,ll k){
    if(s[u].l==s[u].r){s[u].ans+=max(s[u].mx,k)*t;return;}
    if(s[ls].mx>k){
        s[u].ans+=(query(ls,k)+s[u].sum-s[ls].sum)*t;
        put(ls,t,k);
        s[rs].t2+=t;
        s[rs].ans+=(s[u].sum-s[ls].sum)*t;
    }else{
        s[u].ans+=((s[ls].r-s[ls].l+1)*k+query(rs,k))*t;
        put(ls,k*t);
        put(rs,t,k);
    }
}
void pushdown(int u){
    put(ls,s[u].t1);put(rs,s[u].t1);
    if(s[u].t2){
        put(ls,s[u].t2,s[u^1].mx);
        put(rs,s[u].t2,max(s[ls].mx,s[u^1].mx));
    }
    s[u].t1=s[u].t2=0;
}
void build(int u,int l,int r){
    s[u].l=l;s[u].r=r;if(l==r){s[u].mx=s[u].sum=a[l];return;}
    int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);
}
ll qry(int u,int l,int r){
    if(s[u].l>r||s[u].r<l)return 0;
    if(s[u].l>=l&&s[u].r<=r)return s[u].mx;
    pushdown(u);return max(qry(ls,l,r),qry(rs,l,r));//notice pushdown needless
}
ll query(int u,int l,int r){
    if(s[u].l>r||s[u].r<l)return 0;
    if(s[u].l>=l&&s[u].r<=r)return s[u].ans;
    pushdown(u);return query(ls,l,r)+query(rs,l,r);
}
void update(int u,int x,ll k){
    if(s[u].l==s[u].r){s[u].mx=s[u].sum=k;return;}
    pushdown(u);x<=s[ls].r?update(ls,x,k):update(rs,x,k);pushup(u);
}
void update(int u,int l,int r,ll k){
    if(s[u].l>r||s[u].r<l)return;
    if(s[u].l>=l&&s[u].r<=r){put(u,1,k);return;}
    pushdown(u);update(ls,l,r,k);update(rs,l,r,max(k,qry(ls,l,r)));pushup(u);
}
int main(){
    int opt,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)update(1,x,y);
        else if(opt==2)update(1,x,y,0);
        else printf("%lld\n",query(1,x,y));
    }
    return 0;
}

answer.code:102:2: error: stray ‘#’ in program
  102 | }#include<bits/stdc++.h>
      |  ^
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:11: error: ‘bits’ was not declared in this scope
  102 | }#include<bits/stdc++.h>
      |           ^~~~
answer.code:102:16: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
  102 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
answer.code:102:3: error: ‘include’ does not name a type
  102 | }#include<bits/stdc++.h>
      |   ^~~~~~~
answer.code:105:19: error: conflicting declaration ‘typedef long long int ll’
  105 | typedef long long ll;
      |                   ^~
answer.code:27:18: note: previous declaration as ‘typedef __int128 ll’
   27 | typedef __int128 ll;
      |                  ^~
answer.code:106:5: error: redefinition of ‘int n’
  106 | int n,m,a[N];
      |     ^
answer.code:28:5: note: ‘int n’ previously declared here
   28 | int n,m,a[N];
      |     ^
answer.code:106:7: error: redefinition of ‘int m’
  106 | int n,m,a[N];
      |       ^
answer.code:28:7: note: ‘int m’ previously declared here
   28 | int n,m,a[N];
      |       ^
answer.code:106:9: error: redefinition of ‘int a [500005]’
  106 | int n,m,a[N];
      |         ^
answer.code:28:9: note: ‘int a [500005]’ previously declared here
   28 | int n,m,a[N];
      |         ^
answer.code:107:8: error: redefinition of ‘struct seg’
  107 | struct seg{
      |        ^~~
answer.code:29:8: note: previous definition of ‘struct seg’
   29 | struct seg{
      |        ^~~
answer.code:110:2: error: conflicting declaration ‘int s [2000020]’
  110 | }s[N<<2];
      |  ^
answer.code:32:2: note: previous declaration as ‘seg s [2000020]’
   32 | }s[N<<2];
      |  ^
answer.code:113:4: error: redefinition of ‘ll query(int, ll)’
  113 | ll query(int u,ll x){
      |    ^~~~~
answer.code:35:4: note: ‘ll query(int, ll)’ previously defined here
   35 | ll query(int u,ll x){
      |    ^~~~~
answer.code:118:6: error: redefinition of ‘void pushup(int)’
  118 | void pushup(int u){
      |      ^~~~~~
answer.code:40:6: note: ‘void pushup(int)’ previously defined here
   40 | void pushup(int u){
      |      ^~~~~~
answer.code:123:6: error: redefinition of ‘void put(int, ll)’
  123 | void put(int u,ll k){s[u].ans+=k*(s[u].r-s[u].l+1);s[u].t1+=k;}
      |      ^~~
answer.code:45:6: note: ‘void put(int, ll)’ previously defined here
   45 | void put(int u,ll k){s[u].ans+=k*(s[u].r-s[u].l+1);s[u].t1+=k;}
      |      ^~~
answer.code:124:6: error: redefinition of ‘void put(int, ll, ll)’
  124 | void put(int u,ll t,ll k){
      |      ^~~
answer.code:46:6: note: ‘void put(int, ll, ll)’ previou...