/**
 * @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 Q1 {
  int l = -1, r = -1;
  int ind = 0;
};
struct Q {
  int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
  Q1 rr, rl, lr, ll;
};

namespace MO {
std::vector<Q1> qq;
std::vector<int64_t> ans;
void insert(Q1 &q) {
  q.ind = (int)qq.size() + 1;
  qq.push_back(q);
}
void init() {
  BIT<int64_t> v1(m), v2(m);
  BIT<int> f1(m), f2(m);
  int k = (int)qq.size();
  std::sort(qq.begin(), qq.end(), [&](auto a, auto b) {
    return (a.l / B == b.l / B) ? a.r < b.r : a.l < b.l;
  });
  ans.resize(k + 1);
  for (int i = 0; i <= qq[0].l; ++i) {
    v1.add(aa[i], a[i]);
    f1.add(aa[i], 1);
  }
  for (int i = 0; i <= qq[0].r; ++i) {
    ans[qq[0].ind] += (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
                      (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
    v2.add(aa[i], a[i]);
    f2.add(aa[i], 1);
  }
  for (int j = 1; j < k; ++j) {
    // transition from i - 1 to i
    ans[qq[j].ind] = ans[qq[j - 1].ind];
    bool ll = qq[j].l < qq[j - 1].l;
    bool rr = qq[j - 1].r < qq[j].r;
    if (ll) {
      for (int i = qq[j - 1].l; i > qq[j].l; --i) {
        ans[qq[j].ind] -=
            (v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
            (f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
        v1.add(aa[i], -a[i]);
        f1.add(aa[i], -1);
      }
      if (rr) {
        for (int i = qq[j - 1].r + 1; i <= qq[j].r; ++i) {
          ans[qq[j].ind] +=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], a[i]);
          f2.add(aa[i], 1);
        }
      } else {
        for (int i = qq[j - 1].r; i > qq[j].r; --i) {
          ans[qq[j].ind] -=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], -a[i]);
          f2.add(aa[i], -1);
        }
      }
    } else {
      if (rr) {
        for (int i = qq[j - 1].r + 1; i <= qq[j].r; ++i) {
          ans[qq[j].ind] +=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], a[i]);
          f2.add(aa[i], 1);
        }
      } else {
        for (int i = qq[j - 1].r; i > qq[j].r; --i) {
          ans[qq[j].ind] -=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], -a[i]);
          f2.add(aa[i], -1);
        }
      }
      if (ll) {
        for (int i = qq[j - 1].l; i > qq[j].l; --i) {
          ans[qq[j].ind] -=
              (v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
              (f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
          v1.add(aa[i], -a[i]);
          f1.add(aa[i], -1);
        }
      } else {
        for (int i = qq[j - 1].l + 1; i <= qq[j].l; ++i) {
          ans[qq[j].ind] +=
              (v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
              (f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
          v1.add(aa[i], a[i]);
          f1.add(aa[i], 1);
        }
      }
    }
  }
}
}; // 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 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';
  }
}