#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long maxn = 2e5 + 7;
const int maxm = 8e6;
const long long maxe = 1e6 + 7;
const long long INF = 1e9 + 7;
const double PI = acos(-1);
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
inline void Max(int &a, int b) {
  if (b > a) a = b;
}
inline void Min(int &a, int b) {
  if (a == -1 || b < a) a = b;
}
int n, m;
int ls[maxm], rs[maxm], cnt[maxm], tot, root[maxn];
int a[maxn];
int size = 0;
void build(int &rt, int l, int r) {
  rt = tot++;
  cnt[rt] = 0;
  if (l == r) return;
  build(ls[rt], l, (l + r) / 2);
  build(rs[rt], (l + r) / 2 + 1, r);
}
void update(int &rt, int l, int r, int last, int x) {
  rt = tot++;
  cnt[rt] = cnt[last] + 1;
  ls[rt] = ls[last];
  rs[rt] = rs[last];
  if (l == r) return;
  int m = (l + r) >> 1;
  if (x <= m)
    update(ls[rt], l, (l + r) / 2, ls[last], x);
  else
    update(rs[rt], (l + r) / 2 + 1, r, rs[last], x);
}
int query(int rt, int l, int r, int ss, int a, int b) {
  if (a > b) return 0;
  if (r < a || l > b) return 0;
  if (l >= a && r <= b)
    return cnt[rt] - cnt[ss];
  else
    return query(ls[rt], l, (l + r) / 2, ls[ss], a, b) +
           query(rs[rt], (l + r) / 2 + 1, r, rs[ss], a, b);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build(root[0], 1, n);
  for (int i = 1; i <= n; i++) {
    update(root[i], 1, n, root[i - 1], a[i]);
  }
  for (int i = 0; i < m; i++) {
    int l, d, r, u;
    scanf("%d%d%d%d", &l, &d, &r, &u);
    swap(l, d);
    swap(u, r);
    long long r1 = query(root[d - 1], 1, n, root[0], 1, l - 1);
    long long r2 = query(root[d - 1], 1, n, root[0], l, r);
    long long r3 = query(root[d - 1], 1, n, root[0], r + 1, n);
    long long r4 = query(root[u], 1, n, root[d - 1], 1, l - 1);
    long long r5 = query(root[u], 1, n, root[d - 1], l, r);
    long long r6 = query(root[u], 1, n, root[d - 1], r + 1, n);
    long long r7 = query(root[n], 1, n, root[u], 1, l - 1);
    long long r8 = query(root[n], 1, n, root[u], l, r);
    long long r9 = query(root[n], 1, n, root[u], r + 1, n);
    long long sum = r1 + r2 + r3 + r4 + r5 + r6 + r7 + r8 + r9;
    long long ans = r1 * (r5 + r6 + r8 + r9);
    ans += r2 * (sum - r1 - r3 - r2);
    ans += r3 * (r5 + r4 + r7 + r8);
    ans += r4 * (sum - r1 - r7 - r4);
    ans += r5 * (sum - r5);
    ans += r6 * (sum - r3 - r9 - r6);
    ans += r7 * (r2 + r3 + r5 + r6);
    ans += r8 * (sum - r7 - r9 - r8);
    ans += r9 * (r1 + r2 + r4 + r5);
    ans /= 2;
    ans += r5 * (r5 - 1) / 2;
    printf("%lld\n", ans);
  }
  return 0;
}
