#include<bits/stdc++.h>
using namespace std;
using i128=__int128;
int n,m;
namespace ds{
int mx[500010<<2];
i128 len[500010<<2],sum[500010<<2],s0[500010<<2],rs0[500010<<2],tag1[500010<<2],tag2[500010<<2];
i128 dfs1(int u,int l,int r,int x){
   if(l==r)return max(x,mx[u]);
   int mid=l+r>>1;
   if(x>mx[u<<1])return x*len[u<<1]+dfs1(u<<1|1,mid+1,r,x);
   else return dfs1(u<<1,l,mid,x)+rs0[u<<1|1];
}
inline void pushupa(int u,int l,int r){
   int mid=l+r>>1;
   mx[u]=max(mx[u<<1],mx[u<<1|1]);
   rs0[u]=dfs1(u<<1|1,mid+1,r,mx[u<<1]);
   s0[u]=s0[u<<1]+rs0[u];
}
inline void addv(int u,i128 x){
   tag1[u]+=x,sum[u]+=len[u]*x;
}
inline void addm(int u,i128 x){
   tag2[u]+=x,sum[u]+=rs0[u>>1]*x;
}
inline void pushupb(int u){
   sum[u]=sum[u<<1]+sum[u<<1|1]+tag1[u]*len[u]+tag2[u]*rs0[u>>1];
}
void dfs2(int u,int l,int r,int x,i128 w){
   if(l==r)return addv(u,w*max(x,mx[u])),void();
   int mid=l+r>>1;
   if(x>mx[u<<1]){
      addv(u<<1,x*w);
      dfs2(u<<1|1,mid+1,r,x,w);
   }else{
      dfs2(u<<1,l,mid,x,w);
      addm(u<<1|1,w);
   }
   pushupb(u);
}
inline void pushdown(int u,int l,int r){
   addv(u<<1,tag1[u]),addv(u<<1|1,tag1[u]);
   if(u&1)dfs2(u,l,r,mx[u-1],tag2[u]);
   tag1[u]=tag2[u]=0;
}
void mdf(int u,int l,int r,int p,int x){
   if(l==r)return mx[u]=x,void();
   int mid=l+r>>1;pushdown(u,l,r);
   if(p<=mid)mdf(u<<1,l,mid,p,x);
   else mdf(u<<1|1,mid+1,r,p,x);
   pushupa(u,l,r);
}
int opt2(int u,int l,int r,int L,int R,int x){
   if(L<=l&&r<=R){
      dfs2(u,l,r,x,1);
      return max(mx[u],x);
   }
   int mid=l+r>>1;
   if(L<=mid)x=opt2(u<<1,l,mid,L,R,x);
   if(R>mid)x=opt2(u<<1|1,mid+1,r,L,R,x);
   pushupb(u);
   return x;
}
i128 qry(int u,int l,int r,int L,int R){
   if(L<=l&&r<=R)return sum[u];
   int mid=l+r>>1;pushdown(u,l,r);
   i128 res=(L<=mid?qry(u<<1,l,mid,L,R):0)+(R>mid?qry(u<<1|1,mid+1,r,L,R):0);
   pushupb(u);
   return res;
}
void build(int u,int l,int r){
   len[u]=r-l+1;
   if(l==r){
      scanf("%d",&mx[u]),s0[u]=mx[u];
      return;
   }
   int mid=l+r>>1;
   build(u<<1,l,mid),build(u<<1|1,mid+1,r);
   pushupa(u,l,r);
}
}
void wr(i128 x){
   if(x>9)wr(x/10);
   putchar(x%10+'0');
}
int main(){
   scanf("%d%d",&n,&m);
   ds::build(1,1,n);
   for(int op,x,y;m--;){
      scanf("%d%d%d",&op,&x,&y);
      if(op==1)ds::mdf(1,1,n,x,y);
      if(op==2)ds::opt2(1,1,n,x,y,0);
      if(op==3)wr(ds::qry(1,1,n,x,y)),puts("");
   }
   return 0;
}