/**
 * @file qoj4037-1.cpp
 * @author n685
 * @brief
 * @date 2023-09-06
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

#ifdef LOCAL
#include "dd/debug.h"
#define dbg(...) lineInfo(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
#define dbgR(...) lineInfo(__LINE__, #__VA_ARGS__), dbg2(__VA_ARGS__)
#define dbgP(p, ...)                                                           \
  lineInfo(__LINE__, #__VA_ARGS__ " proj"), dbg3(p, __VA_ARGS__)
#define dbgRP(p, ...)                                                          \
  lineInfo(__LINE__, #__VA_ARGS__ " proj"), dbg4(p, __VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class T> struct CC {
  std::vector<T> val;
  void push(T a) { val.push_back(a); }
  void init() {
    std::sort(val.begin(), val.end());
    val.erase(std::unique(val.begin(), val.end()), val.end());
  }
  int operator[](T a) const {
    return static_cast<int>(std::distance(
        val.begin(), std::lower_bound(val.begin(), val.end(), a)));
  }
  int size() const { return static_cast<int>(val.size()); }
};

#ifndef LOCAL
constexpr int B = 300;
#else
constexpr int B = 2;
#endif

template <class T> struct BIT {
  int sz;
  std::vector<T> val;
  BIT() : sz(0) {}
  BIT(int _sz) : sz(_sz), val(sz + 1) {}
  void add(int i, T a) {
    i++;
    for (; i <= sz; i += (i & -i)) {
      val[i] += a;
    }
  }
  T sum(int i) {
    i++;
    T ans = 0;
    for (; i > 0; i -= (i & -i)) {
      ans += val[i];
    }
    return ans;
  }
  T query(int a, int b) { return sum(b) - sum(a - 1); }
};
// upd: O(sqrt(N)), query: O(1)
template <class T> struct PURQ {
  int sz, bSz;
  std::vector<T> val, bl;
  PURQ(int _sz)
      : sz(_sz), bSz((_sz + B - 1) / B), val(_sz), bl((_sz + B - 1) / B) {}
  void add(int i, T a) {
    for (; i < sz && i % B != 0; ++i) {
      val[i] += a;
    }
    if (i == sz) {
      return;
    }
    i /= B;
    for (; i < bSz; ++i) {
      bl[i] += a;
    }
  }
  T sum(int i) {
    if (i < 0) {
      return 0;
    }
    return val[i] + bl[i / B];
  }
  T query(int a, int b) {
    if (a > b) {
      return 0;
    }
    return sum(b) - sum(a - 1);
  }
};

int n, q;
int m;
std::vector<int64_t> a;
std::vector<int> aa;

struct Q2 {
  int l1 = -1, l2 = -1, r1 = -1, r2 = -1;
  int ind = 0;
};
struct Q1 {
  int l = -1, r = -1;
  int ind = 0;
  Q2 lr, rr;
};
struct Q {
  int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
  Q1 rr, rl, lr, ll;
};

namespace LRL {
std::vector<int64_t> p;
void init() {
  BIT<int> freq(m);
  BIT<int64_t> val(m);
  p.resize(n + 1);
  for (int i = 0; i < n; ++i) {
    freq.add(aa[i], 1);
    val.add(aa[i], a[i]);
    for (int i = 0; i < n; ++i) {
      p[i] = (val.query(aa[i], m - 1) - freq.query(aa[i], m - 1) * a[i]) +
             (freq.query(0, aa[i] - 1) * a[i] - val.query(0, aa[i] - 1));
      if (i > 0) {
        p[i] += p[i - 1];
      }
    }
  }
}
int64_t query(int l, int r) {
  if (l == 0) {
    return p[r];
  }
  return p[r] - p[l - 1];
}
}; // namespace LRL

namespace LRR {
std::vector<int64_t> ans;
std::vector<Q2> v;
void insert(Q2 &q) {
  assert(q.r2 == n - 1);
  q.ind = (int)v.size() + 1;
  v.push_back(q);
}
void init() {
  std::sort(v.begin(), v.end(), [&](auto a, auto b) { return a.r1 > b.r1; });
  ans.resize((int)v.size() + 1);
  PURQ<int> freq(m);
  PURQ<int64_t> val(m);
  for (int i = 0; i < (int)v.size(); ++i) {
    for (int j = (i == 0 ? n - 1 : v[i - 1].r1 - 1); j >= v[i].r1; --j) {
      freq.add(aa[j], 1);
      val.add(aa[j], a[j]);
    }
    for (int j = v[i].l1; j <= v[i].l2; ++j) {
      ans[v[i].ind] +=
          (val.query(aa[j], m - 1) - freq.query(aa[j], m - 1) * a[j]) +
          (freq.query(0, aa[j] - 1) * a[j] - val.query(0, aa[j] - 1));
    }
  }
}
}; // namespace LRR

namespace MO {
std::vector<Q1> q2;
std::vector<int64_t> ans;
void insert(Q1 &q) {
  q.ind = (int)q2.size() + 1;
  q2.push_back(q);
}
void init() {
  int k = (int)q2.size();
  std::sort(q2.begin(), q2.end(), [&](auto a, auto b) {
    return (a.l / B == b.l / B) ? a.r < b.r : a.l < b.l;
  });
  q2[0].rr = Q2{0, q2[0].l, q2[0].r + 1, n - 1};
  LRR::insert(q2[0].rr);
  for (int i = 1; i < k; ++i) {
    bool ll = q2[i].l < q2[i - 1].l;
    bool rr = q2[i].r > q2[i - 1].r;
    if (ll) {
      if (q2[i - 1].r != n - 1) {
        q2[i].lr = Q2{q2[i].l + 1, q2[i - 1].l, q2[i - 1].r + 1, n - 1},
        LRR::insert(q2[i].lr);
      }
      if (q2[i - 1].r != q2[i].r && q2[i].l != n - 1) {
        if (rr) {
          q2[i].rr = Q2{q2[i - 1].r + 1, q2[i].r, q2[i].l + 1, n - 1};
        } else {
          q2[i].rr = Q2{q2[i].r + 1, q2[i - 1].r, q2[i].l + 1, n - 1};
        }
        LRR::insert(q2[i].rr);
      }
    } else {
      if (q2[i - 1].r != q2[i].r && q2[i - 1].l != n - 1) {
        if (rr) {
          q2[i].rr = Q2{q2[i - 1].r + 1, q2[i].r, q2[i - 1].l + 1, n - 1};
        } else {
          q2[i].rr = Q2{q2[i].r + 1, q2[i - 1].r, q2[i - 1].l + 1, n - 1};
        }
        LRR::insert(q2[i].rr);
      }
      if (q2[i - 1].l != q2[i].l && q2[i - 1].r != n - 1) {
        if (ll) {
          q2[i].lr = Q2{q2[i].l + 1, q2[i - 1].l, q2[i].r + 1, n - 1};
        } else {
          q2[i].lr = Q2{q2[i - 1].l + 1, q2[i].l, q2[i].r + 1, n - 1};
        }
        LRR::insert(q2[i].lr);
      }
    }
  }
  LRL::init();
  LRR::init();
  ans.resize(k + 1);
  ans[q2[0].ind] = LRL::query(0, q2[0].l) - LRR::ans[q2[0].rr.ind];
  for (int i = 1; i < k; ++i) {
    ans[q2[i].ind] += ans[q2[i - 1].ind];
    bool ll = q2[i].l < q2[i - 1].l;
    bool rr = q2[i].r > q2[i - 1].r;
    if (ll) {
      ans[q2[i].ind] -=
          LRL::query(q2[i].l + 1, q2[i - 1].l) - LRR::ans[q2[i].lr.ind];
      if (q2[i].r != q2[i - 1].r) {
        if (rr) {
          ans[q2[i].ind] +=
              LRL::query(q2[i - 1].r + 1, q2[i].r) - LRR::ans[q2[i].rr.ind];
        } else {
          ans[q2[i].ind] -=
              LRL::query(q2[i].r + 1, q2[i - 1].r) - LRR::ans[q2[i].rr.ind];
        }
      }
    } else {
      if (q2[i].r != q2[i - 1].r) {
        if (rr) {
          ans[q2[i].ind] +=
              LRL::query(q2[i - 1].r + 1, q2[i].r) - LRR::ans[q2[i].rr.ind];
        } else {
          ans[q2[i].ind] -=
              LRL::query(q2[i].r + 1, q2[i - 1].r) - LRR::ans[q2[i].rr.ind];
        }
      }
      if (q2[i].l != q2[i - 1].l) {
        if (ll) {
          ans[q2[i].ind] -=
              LRL::query(q2[i].l + 1, q2[i - 1].l) - LRR::ans[q2[i].lr.ind];
        } else {
          ans[q2[i].ind] +=
              LRL::query(q2[i - 1].l + 1, q2[i].l) - LRR::ans[q2[i].lr.ind];
        }
      }
    }
  }
}
}; // namespace MO

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  cin >> n >> q;
  a.resize(n);
  CC<int64_t> cc;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    cc.push(a[i]);
  }
  cc.init();
  m = cc.size();
  aa.resize(n);
  for (int i = 0; i < n; ++i) {
    aa[i] = cc[a[i]];
  }
  std::vector<Q> qq(q);
  std::vector<Q1> q2;
  auto insert = [&](Q1 &q) {
    q.ind = (int)q2.size() + 1;
    q2.push_back(q);
  };
  auto create = [&](int a, int b) {
    return Q1{std::min(a, b), std::max(a, b)};
  };
  for (int i = 0; i < q; ++i) {
    cin >> qq[i].l1 >> qq[i].r1 >> qq[i].l2 >> qq[i].r2;
    qq[i].l1--;
    qq[i].l2--;
    qq[i].r1--;
    qq[i].r2--;
    qq[i].rr = create(qq[i].r1, qq[i].r2);
    MO::insert(qq[i].rr);
    if (qq[i].l2 > 0) {
      qq[i].rl = create(qq[i].r1, qq[i].l2 - 1);
      MO::insert(qq[i].rl);
    }
    if (qq[i].l1 > 0) {
      qq[i].lr = create(qq[i].l1 - 1, qq[i].r1);
      MO::insert(qq[i].lr);
    }
    if (qq[i].l1 > 0 && qq[i].l2 > 0) {
      qq[i].ll = create(qq[i].l1 - 1, qq[i].l2 - 1);
      MO::insert(qq[i].ll);
    }
  }
  MO::init();
  std::vector<int64_t> ans(q);
  for (int i = 0; i < q; ++i) {
    ans[i] = MO::ans[qq[i].rr.ind] - MO::ans[qq[i].rl.ind] -
             MO::ans[qq[i].lr.ind] + MO::ans[qq[i].ll.ind];
    cout << ans[i] << '\n';
  }
}