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

#define Gene template< class
#define Rics printer& operator,
Gene c> struct rge{c b, e;};
Gene c> rge<c> range(c i, c j){ return {i, j};}
struct printer{
    ~printer(){cerr<<endl;}
    Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
    Rics(string x){cerr<<x;return *this;}
    Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
    Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
    Gene c >Rics(rge<c> x){
        *this,"["; for(auto it = x.b; it != x.e; ++it)
            *this,(it==x.b?"":", "),*it; return *this,"]";}
};
#define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
#define dbg(x) "[",#x,": ",(x),"] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r) {
    return uniform_int_distribution<int>(l, r) (rng);
}

const int B = 500;
const int N = 2e5+100;
const int MX = 1e5+10;

struct Query {
    int l1, r1, l2, r2;
};

long long brokenSolve(vector<int>&a, vector<vector<int>>&occ, int l1, int r1, int l2, int r2) {
    long long ans = 0;
    for(int i = l1; i <= r1; i++) {
        int cnt = upper_bound(occ[a[i]].begin(), occ[a[i]].end(), r2) - lower_bound(occ[a[i]].begin(), occ[a[i]].end(), l2);
        ans += cnt;
    }
    return ans;
}

int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<vector<int>> occ(MX);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        occ[a[i]].push_back(i);
    }
    vector<Query> queries(q);
    for(int i = 0; i < q; i++) {
        cin >> queries[i].l1 >> queries[i].r1 >> queries[i].l2 >> queries[i].r2;
        queries[i].l1--;
        queries[i].r1--;
        queries[i].l2--;
        queries[i].r2--;
    }
    vector<long long> ans(q);
    for(int l = 0; l < n; l += B) {
        int r = l+B-1;
        if(r >= n) break;
//        debug(), dbg(l), dbg(r);
        vector<int> cnt(MX);
        for(int i = l; i <= r; i++) cnt[a[i]]++;
        vector<long long> pref(n);
        for(int i = 0; i < n; i++) pref[i] = (i>0 ? pref[i-1]:0) + cnt[a[i]];
        for(int i = 0; i < q; i++) {
            if(queries[i].l1 <= l && queries[i].r1 >= r) {
                ans[i] += pref[queries[i].r2] - (queries[i].l2 > 0 ? pref[queries[i].l2-1] : 0);
            }
        }
    }
//    for(int i = 0; i < q; i++) {
//        cout << ans[i] << "\n";
//    }
    for(int i = 0; i < q; i++) {
        int lb = queries[i].l1/B, rb = queries[i].r1/B;
        if(lb == rb) {
            if(queries[i].r1-queries[i].l1+1 < B) {
                ans[i] += brokenSolve(a, occ, queries[i].l1, queries[i].r1, queries[i].l2, queries[i].r2);
            }
        }
        else {
            if(queries[i].l1%B > 0) ans[i] += brokenSolve(a, occ, queries[i].l1,(lb+1)*B-1, queries[i].l2, queries[i].r2);
            if((queries[i].r1+1)%B > 0) ans[i] += brokenSolve(a, occ, rb*B, queries[i].r1, queries[i].l2, queries[i].r2);
        }
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}