#include<iostream>
#include<cstdio>
#define N 500000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,m,a[N+1];
struct seg
{
	struct node
	{
		int l,r,maxn,lazy2;
		long long lazy,data;
		__int128 res;
	};
	node tree[(N<<2)+1];
	int smaxn;
	long long calc(int k,int d)
	{
		if (d>=tree[k].maxn) return 1ll*d*(tree[k].r-tree[k].l+1);
		if (tree[k].l==tree[k].r) return tree[k].maxn;
		if (d>=tree[k<<1].maxn) return 1ll*d*(tree[k<<1].r-tree[k<<1].l+1)+calc(k<<1|1,d);
		else return calc(k<<1,d)+tree[k].data-tree[k<<1].data;
	}
	void push_up(int k)
	{
		tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn),tree[k].data=tree[k<<1].data+calc(k<<1|1,tree[k<<1].maxn);
		return;
	}
	void push_up2(int k)
	{
		tree[k].res=tree[k<<1].res+tree[k<<1|1].res;
		return;
	}
	void push_tag(int k,long long d)
	{
		tree[k].res+=(__int128)(d)*(tree[k].r-tree[k].l+1),tree[k].lazy+=d;
		return;
	}
	void push_tag2(int k,int d)
	{
		tree[k].res+=tree[k].data-tree[k<<1].data,tree[k].lazy2+=d;
		return;
	}
	void push_tag3(int k,int d,int d2,long long &rst)
	{
		if (d>=tree[k].maxn)
		{
			push_tag(k,1ll*d*d2),rst=1ll*d*(tree[k].r-tree[k].l+1);
			return;
		}
		if (tree[k].l==tree[k].r) tree[k].res+=1ll*tree[k].maxn*d2,rst=tree[k].maxn;
		else
		{
			long long dst=0;
			if (d>=tree[k<<1].maxn) push_tag(k<<1,1ll*d*d2),push_tag3(k<<1|1,d,d2,dst),rst=1ll*d*(tree[k<<1].r-tree[k<<1].l+1)+dst;
			else tree[k].lazy2+=d2,push_tag3(k<<1,d,d2,dst),rst=tree[k].data-tree[k<<1].data+dst;
			tree[k].res+=(__int128)(rst)*d2;
		}
		return;
	}
	void spread(int k)
	{
		long long dst=0;
		if (tree[k].lazy) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
		if (tree[k].lazy2) push_tag3(k<<1|1,tree[k<<1].maxn,tree[k].lazy2,dst),tree[k].lazy2=0;
		return;
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r)
		{
			tree[k].maxn=tree[k].data=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;
	}
	void change(int k,int x,int d)
	{
		if (tree[k].l==tree[k].r)
		{
			tree[k].maxn=tree[k].data=d;
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (x<=mid) change(k<<1,x,d);
		else change(k<<1|1,x,d);
		push_up(k);
		return;
	}
	void solve(int k,int l,int r)
	{
		long long dst=0;
		if (tree[k].l==l&&tree[k].r==r)
		{
			push_tag3(k,smaxn,1,dst),smaxn=max(smaxn,tree[k].maxn);
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) solve(k<<1,l,r);
		else if (l>=mid+1) solve(k<<1|1,l,r);
		else solve(k<<1,l,mid),solve(k<<1|1,mid+1,r);
		push_up2(k);
		return;
	}
	__int128 query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].res;
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
	}
};
seg T;
void write(__int128 x)
{
	if (!x) return;
	write(x/10),printf("%d",(int)(x%10));
	return;
}
int main()
{
	int op,x,y,l,r;
	__int128 d;
	n=read(),m=read();
	for (int i=1;i<=n;++i) a[i]=read();
	T.build(1,1,n);
	while (m--)
	{
		op=read();
		if (op==1) x=read(),y=read(),T.change(1,x,y);
		else if (op==2)
		{
			l=read(),r=read();
			if (l<=r) T.smaxn=0,T.solve(1,l,r);
		}
		else
		{
			l=read(),r=read(),d=T.query(1,l,r);
			if (!d) puts("0");
			else write(d),puts("");
		}
	}
	return 0;
}