#include<cstdio>
#include<algorithm>
const int N=5e5+7;
typedef long long ll;
ll tr[N*4];int sz[N*4],lza[N*4],lzb[N*4];
ll sm[N*4];int szz[N*4],lzv[N*4],mn[N*4],a[N],n;
void build(int l,int r,int rt)
{
	szz[rt]=r-l+1;lza[rt]=1;
	if(l==r){tr[rt]=0;sm[rt]=mn[rt]=a[l];return;}
	int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
	mn[rt]=std::min(mn[rt<<1],mn[rt<<1|1]);
	sm[rt]=sm[rt<<1]+sm[rt<<1|1];
}
inline void achg(int x,int a,int b)
{
	tr[x]=tr[x]*a+(ll)b*sz[x];
	lza[x]*=a;lzb[x]=lzb[x]*a+b;
}
inline void apush(int x){if(lza[x]!=1||lzb[x])achg(x<<1,lza[x],lzb[x]),achg(x<<1|1,lza[x],lzb[x]),lza[x]=1,lzb[x]=0;}
void aupd(int L,int R,int v,int l,int r,int rt)
{
	if(L<=l&&r<=R)return achg(rt,-1,v);
	int mid=(l+r)>>1;apush(rt);
	if(L<=mid)aupd(L,R,v,l,mid,rt<<1);
	if(R>mid)aupd(L,R,v,mid+1,r,rt<<1|1);
	sz[rt]=sz[rt<<1]+sz[rt<<1|1];
	tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
void mdf(int p,int v,int l,int r,int rt)
{
	if(l==r){tr[rt]=v;sz[rt]=1;return;}
	int mid=(l+r)>>1;apush(rt);
	if(p<=mid)mdf(p,v,l,mid,rt<<1);
	else mdf(p,v,mid+1,r,rt<<1|1);
	sz[rt]=sz[rt<<1]+sz[rt<<1|1];
	tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
inline void bchg(int x,int v){/*printf("bcs %d %d\n",x,v)*/;sm[x]-=(ll)v*szz[x];mn[x]-=v;lzv[x]+=v;}
inline void bpush(int x){if(lzv[x])bchg(x<<1,lzv[x]),bchg(x<<1|1,lzv[x]),lzv[x]=0;}
void bupd(int L,int R,int v,int l,int r,int rt)
{
//	printf("mn[%d,%d]=%d\n",l,r,mn[rt]);
	if(!szz[rt])return;
	if(L<=l&&r<=R&&mn[rt]>=v)return bchg(rt,v);
	if(l==r){mdf(l,v-sm[rt],1,n,1);szz[rt]=sm[rt]=0;mn[rt]=1e9;return;}
	int mid=(l+r)>>1;bpush(rt);
	if(L<=mid)bupd(L,R,v,l,mid,rt<<1);
	if(R>mid)bupd(L,R,v,mid+1,r,rt<<1|1);
	szz[rt]=szz[rt<<1]+szz[rt<<1|1];
	sm[rt]=sm[rt<<1]+sm[rt<<1|1];
	mn[rt]=std::min(mn[rt<<1],mn[rt<<1|1]);
}
ll qr(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)return tr[rt]+sm[rt];
	int mid=(l+r)>>1;ll ans=0;apush(rt);bpush(rt);
	if(L<=mid)ans=qr(L,R,l,mid,rt<<1);
	if(R>mid)ans+=qr(L,R,mid+1,r,rt<<1|1);
	return ans;
}
int main()
{
	int q;scanf("%d%d",&n,&q);for(int i=1;i<=n;++i)scanf("%d",a+i);
	build(1,n,1);while(q--)
	{
		int o,l,r,x;scanf("%d%d%d",&o,&l,&r);
		if(o==1)scanf("%d",&x),aupd(l,r,x,1,n,1),bupd(l,r,x,1,n,1);
		else printf("%lld\n",qr(l,r,1,n,1));
	}
	return 0;
}