#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
// Cope Counter = at least 205
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct qry {
  ll l, r, i, t;
  qry() {
    l = r = i = t = 0;
  }
  qry(ll a, ll b, ll c, ll d) {
    l = a, r = b, i = c, t = d;
  }
};
bool comp(qry &a, qry &b) {
  if(a.l / 321 == b.l / 321) return a.r < b.r;
  return a.l < b.l;
}
ll n, q;
struct sqd {
  ll block[321], sum[100321];
  void clear() {
    for(ll i = 0; i < 321; i++) block[i] = 0;
    for(ll i = 0; i < 1e5 + 321; i++) sum[i] = 0;
  }
  sqd() {
    clear();
  }
  void update(ll i, ll x) {
    for(ll j = i / 321 + 1; j < 321; j++) block[j] += x;
    for(ll j = i; j < (i / 321 + 1) * 321; j++) sum[j] += x;
  }
  ll query(ll i) {
    if(i < 0) return 0;
    return block[i / 321] + sum[i];
  }
};

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  pair<ll, ll> arr[n];
  for(ll i = 0; i < n; i++) {
    cin >> arr[i].f;
    arr[i].s = i;
  }
  sort(arr, arr + n);
  ll cur = 0;
  ll a[n];
  for(ll i = 0; i < n; i++) {
    if(i > 0 && arr[i].f != arr[i - 1].f) cur++;
    a[arr[i].s] = cur;
  }
  vector<qry> qrys;
  ll l1, r1, l2, r2;
  for(ll i = 0; i < q; i++) {
    cin >> l1 >> r1 >> l2 >> r2;
    l1--, r1--, l2--, r2--;
    qrys.push_back(qry(r1, r2, i, 1));
    if(l1 > 0) qrys.push_back(qry(l1 - 1, r2, i, -1));
    if(l2 > 0) qrys.push_back(qry(r1, l2 - 1, i, -1));
    if(l1 > 0 && l2 > 0) qrys.push_back(qry(l1 - 1, l2 - 1, i, 1));
  }
  sort(qrys.begin(), qrys.end(), comp);
  ll l = 0, r = 0;
  vector<qry> kms[n];
  ll d[qrys.size()];
  for(ll i = 0; i < qrys.size(); i++) {
    d[i] = 0;
    if(qrys[i].r > r) kms[l].push_back(qry(r + 1, qrys[i].r, i, 1));
    if(qrys[i].r < r) kms[l].push_back(qry(qrys[i].r + 1, r, i, -1));
    if(qrys[i].l > l) kms[qrys[i].r].push_back(qry(l + 1, qrys[i].l, i, 1));
    if(qrys[i].l < l) kms[qrys[i].r].push_back(qry(qrys[i].l + 1, l, i, -1));
    l = qrys[i].l, r = qrys[i].r;
  }
  sqd cnt, sum;
  cur = 0;
  for(ll i = 0; i < n; i++) {
    cnt.update(a[i], 1);
    sum.update(a[i], arr[i].f);
    cur += arr[i].f;
    for(qry j : kms[i]) {
      for(ll k = j.l; k <= j.r; k++) {
        d[j.i] += j.t * (arr[k].f * (2 * cnt.query(a[k]) - i - 1) + cur - 2 * sum.query(a[k]));
      }
    }
  }
  cur = 0;
  ll ans[q];
  for(ll i = 0; i < q; i++) ans[i] = 0;
  for(ll i = 0; i < qrys.size(); i++) {
    cur += d[i];
    ans[qrys[i].i] += qrys[i].t * cur;
  }
  for(ll i = 0; i < q; i++) cout << ans[i] << "\n";
}