#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
int n,q,n1,n2,a[N],ca[N<<1],ql[N],qr[N],qx[N],hp[N<<1],hq[N<<1],pn[N],pv[N],qn[N],qi[N],cnt;
ll c1[N],c2[N],ans[N];

void init(int n){
    n1=n;
    n2=n;
    memset(c1,0,sizeof(c1));
    memset(c2,0,sizeof(c2));
}

void add1(int p,ll x){
    for(int i=p;i<=n1;i+=i&-i){
    	c1[i]+=x;
	}
}

void add2(int p,ll x){
    for(int i=p;i<=n2;i+=i&-i){
    	c2[i]+=x;
	}
}

ll sum1(int p){
	ll v=0;
	for(int i=p;i;i-=i&-i) v+=c1[i];
	return v;
}

ll sum2(int p){
	ll v=0;
	for(int i=p;i;i-=i&-i) v+=c2[i];
	return v;
}

int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		ca[i]=a[i];
	}
	for(int i=1;i<=q;i++){
		int op;
		scanf("%d%d%d%d",&op,&ql[i],&qr[i],&qx[i]);
		ca[n+i]=qx[i];
	}
	sort(ca+1,ca+n+q+1);
    int m=unique(ca+1,ca+n+q+1)-ca-1;
    memset(hp,-1,sizeof(hp));
    memset(hq,-1,sizeof(hq));
    for(int i=1;i<=n;i++){
        int idx=lower_bound(ca+1,ca+m+1,a[i])-ca;
        pv[i]=i;
        pn[i]=hp[idx];
        hp[idx]=i;
    }
    for(int i=1;i<=q;i++){
    	int idx=lower_bound(ca+1,ca+m+1,qx[i])-ca;
    	qi[i]=i;
    	qn[i]=hq[idx];
    	hq[idx]=i;
	}
	init(n);
	for(int i=m;i>=1;i--){
		for(int p=hp[i];p!=-1;p=pn[p]){
			int pos=pv[p];
			add1(pos,a[pos]);
			add2(pos,1);
		}
		for(int p=hq[i];p!=-1;p=qn[p]){
			int x=qi[p];
			ans[x]=sum1(qr[x])-sum1(ql[x]-1)-(sum2(qr[x])-sum2(ql[x]-1))*qx[x];
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}