#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; //template #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(a);i>(b);i--) #define ALL(v) (v).begin(),(v).end() typedef long long int ll; typedef pair<ll, ll> P; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);} const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2; //template end int bit[100010],bit2[100010],n; void add(int i,int a){ i++; while(i<=n){ bit[i]+=a; i+=(i&-i); } } ll sum(int i){ ll res=0; i++; while(i){ res+=bit[i]; i-=(i&-i); } return res; } void add2(int i,int a){ i++; while(i<=n){ bit2[i]+=a; i+=(i&-i); } } ll sum2(int i){ ll res=0; i++; while(i){ res+=bit2[i]; i-=(i&-i); } return res; } vector<int> a,x; bool cmp(int i,int j){return a[i]<a[j];} bool cmp2(int i,int j){return x[i]<x[j];} int main(){ int q; cin>>n>>q; a.resize(n); vector<int> pri(n),pri2(q); rep(i,0,n)cin>>a[i]; iota(ALL(pri),0); iota(ALL(pri2),0); sort(ALL(pri),cmp); vector<int> l(q),r(q); x.resize(q); int tmp; rep(i,0,q)cin>>tmp>>l[i]>>r[i]>>x[i]; sort(ALL(pri2),cmp2); int idx=0; rep(i,0,n){add(i,1); add2(i,a[i]);} vector<ll> ans(q); for(int i:pri2){ while(idx<n&&a[pri[idx]]<x[i]){ add(pri[idx],-1); add2(pri[idx],-a[pri[idx]]); idx++; } ans[i]=(sum2(r[i]-1)-sum2(l[i]-2))-x[i]*(sum(r[i]-1)-sum(l[i]-2)); } rep(i,0,q)printf("%lld\n",ans[i]); return 0; }