#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 5e4+5;

int n, q, a[N];

namespace Subtask1 {
    int f1[1005], f2[1005];
    bool check() {
        return n <= 1000 && q <= 1000;
    }
    void solve() {
        while (q--) {
            int x, y, u, v; cin >> x >> y >> u >> v;
            memset(f1, 0, sizeof f1); 
            memset(f2, 0, sizeof f2);
            for (int i = x; i <= y; i++) f1[a[i]]++;
            for (int i = u; i <= v; i++) f2[a[i]]++;
            ll ans = 0;
            for (int i = 1; i <= n; i++) ans += 1LL * f1[i] * f2[i];
            cout << ans << '\n';
        }
    }
}

namespace Subtask2 {
    int P[55][N];
    bool check() {
        return *max_element(a + 1, a + n + 1) <= 50;
    }
    int query(int x, int l, int r) {
        return P[x][r] - P[x][l - 1];
    }
    void solve() {
        for (int x = 1; x <= 50; x++)
            for (int i = 1; i <= n; i++) 
                P[x][i] = P[x][i - 1] + (a[i] == x);
        while (q--) {
            int x, y, u, v; cin >> x >> y >> u >> v;
            ll ans = 0;
            for (int val = 1; val <= 50; val++) 
                ans += 1LL * query(val, x, y) * query(val, u, v);
            cout << ans << '\n';
        }
    }
}

namespace Fulltask {
    int B;
    struct Query {
        int r1, r2, id, sign;
        bool operator<(const Query& o) const {
            int b1 = r1 / B, b2 = o.r1 / B;
            if (b1 != b2) return b1 < b2;
            return (b1 & 1) ? (r2 < o.r2) : (r2 > o.r2);
        }
    };
    int cnt1[N], cnt2[N];
    ll ans[N], cur_ans = 0;
    inline void add1(int p) {
        cur_ans += cnt2[a[p]];
        cnt1[a[p]]++;
    }
    inline void remove1(int p) {
        cnt1[a[p]]--;
        cur_ans -= cnt2[a[p]];
    }
    inline void add2(int p) {
        cur_ans += cnt1[a[p]];
        cnt2[a[p]]++;
    }
    inline void remove2(int p) {
        cnt2[a[p]]--;
        cur_ans -= cnt1[a[p]];
    }
    void solve() {
        vector<Query> qs;
        for (int i = 0; i < q; i++) {
            int x, y, u, v; cin >> x >> y >> u >> v;
            qs.push_back({y, v, i, 1});
            qs.push_back({y, u - 1, i, -1});
            qs.push_back({x - 1, v, i, -1});
            qs.push_back({x - 1, u - 1, i, 1});
        }
        B = max(1, (int)(n / sqrt(4 * q)));
        sort(qs.begin(), qs.end());
        int R1 = 0, R2 = 0;
        for (int i = 0; i < (int)qs.size(); i++) {
            int r1 = qs[i].r1, r2 = qs[i].r2;
            while (R1 < r1) add1(++R1);
            while (R1 > r1) remove1(R1--);
            while (R2 < r2) add2(++R2);
            while (R2 > r2) remove2(R2--);
            ans[qs[i].id] += qs[i].sign * cur_ans;
        }
        for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    }
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (Subtask1::check()) Subtask1::solve();
    else if (Subtask2::check()) Subtask2::solve();
    else Fulltask::solve();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define TASK "DAYSO"
    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    
    int tests = 1; // cin >> tests;
    while (tests--) solve();

    #ifdef LOCAL
    cerr << "\nTime elapsed: " << clock() << " ms.\n";
    #endif
    return 0;
}