#include <bits/stdc++.h> using namespace std; template<int n> struct Segt { int64_t sumv[n * 4]; Segt() { memset(sumv, 0x00, sizeof(sumv)); } void update(int v, int k, int lb = 0, int rb = n, int t = 1) { if (rb - lb == 1) { sumv[t] += v; return; } int mb = lb + rb >> 1; if (k < mb) update(v, k, lb, mb, t << 1); else update(v, k, mb, rb, t << 1 | 1); sumv[t] = sumv[t << 1] + sumv[t << 1 | 1]; } int64_t query(int ql, int qr, int lb = 0, int rb = n, int t = 1) { if (qr <= lb || rb <= ql) return 0LL; if (ql <= lb && rb <= qr) return sumv[t]; int mb = lb + rb >> 1; return query(ql, qr, lb, mb, t << 1) + query(ql, qr, mb, rb, t << 1 | 1); } }; int main() { int N, Q; cin >> N >> Q; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } vector<tuple<int, int, int>> T(Q); for (int i = 0; i < Q; ++i) { int P, L, R, X; cin >> P >> L >> R >> X; T[i] = make_tuple(X, L, R); } vector<int> ord(N + Q); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int i, int j) { auto f = [&](int x) { return x < N ? A[x] : get<0>(T[x - N]); }; return f(i) > f(j); }); vector<int> ans(Q); Segt<(1 << 17)> stree; Segt<(1 << 17)> ctree; for (int i = 0; i < N + Q; ++i) { int o = ord[i]; if (o < N) { stree.update(A[o], o); ctree.update(1, o); } else { int x, l, r; tie(x, l, r) = T[o - N]; ans[o - N] = stree.query(l - 1, r) - ctree.query(l - 1, r) * x; } } for (int i = 0; i < Q; ++i) { cout << ans[i] << endl; } return 0; }