#include <bits/stdc++.h>

using namespace std;

typedef int int2;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vii vector<vector<int>>
#define vpi vector<pi>
#define lep(i,l,r) for(int i=l;i<=r;++i)
#define rep(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define f first
#define s second
const int inf = 1e18;

int t;


const int maxn = 1e5 + 5;
const int B = 400;

int les[maxn], lazy_les[B];
int sum_les[maxn], lazy_sum_les[B];
int tot = 0;
int totsum = 0;
int a[maxn];
vector<int> vals;
int delta[maxn];

struct Query {
    int l, r, idx;
    Query(int _l, int _r, int _idx): l(_l), r(_r), idx(_idx) {}
    bool operator <(const Query &other) {
        int sign = ((l/B)&1) ? 1 : -1;
        return l/B == other.l/B ? sign * r < sign * other.r : l < other.l;
    }
};

void insert(int x) {
    int i;
    for (i = x + 1; i % B != 0; i++) {
        les[i]++;
        sum_les[i] += vals[x];
    }
    for (i /= B; i < B; i++) {
        lazy_les[i]++;
        lazy_sum_les[i]+=vals[x];
    }
    tot++;
    totsum += vals[x];
}

int query_num_less(int x) {
    return les[x]+lazy_les[x/B];
}

int query_num_greater(int x) {
    return tot - query_num_less(x+1);
}

int query_sum_less(int x) {
    return sum_les[x] + lazy_sum_les[x/B];
}

int query_sum_greater(int x) {
    return totsum - query_sum_less(x+1);
}

typedef array<int,4> a4;
vector<a4> rights[maxn], lefts[maxn];

int2 main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    lep(i,1,n) {
        cin >> a[i];
        vals.pb(a[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    lep(i,1,n) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    }
    vector<Query> queries;
    function<void(int,int,int)> make_query = [&](int l, int r, int idx) {
        if (l > r) swap(l,r);
        queries.pb({l,r,idx});
    };
    lep(qq,1,q) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        // need to ensure we consider things in the right order
        make_query(r1,r2,4*qq-3);
        make_query(r1,l2-1,4*qq-2);
        make_query(l1-1,r2,4*qq-1);
        make_query(l1-1,l2-1,4*qq);
    }
    int curl = 0;
    int curr = 0;
    sort(queries.begin(), queries.end());
    for (auto [l, r, idx]: queries) {
        // cout << "l: " << l << ", r: " << r << ", idx: " << idx << "\n";
        if (curr < r) {
            if (curl) lefts[curl].pb({curr,r,+1,idx});
            curr = r;
        }
        if (curl > l) {
            rights[curr].pb({l,curl,-1,idx});
            curl = l;
        }
        // cout << "curl: " << curl << ", curr: " << curr << "\n";
        if (curr > r) {
            if (curl) lefts[curl].pb({r,curr,-1,idx});
            curr = r;
        }
        if (curl < l) {
            rights[curr].pb({curl,l,+1,idx});
            curl=l;
        }
    }
    lep(i,1,n) {
        insert(a[i]);
        // if (!lefts[i].empty() or !rights[i].empty()) {cout << "i: " << i << "\n";}
        // if (!lefts[i].empty()) {cout << "lefts:\n";}
        for (auto [l, r, sign, idx]: lefts[i]) {
            // changing the right boundary
            lep(j,l+1,r) {
                int num_less = query_num_less(a[j]);
                int num_greater = query_num_greater(a[j]);
                int sum_less = query_sum_less(a[j]);
                int sum_greater = query_sum_greater(a[j]);
                int contrib = vals[a[j]] * num_less - sum_less + sum_greater - vals[a[j]] * num_greater;
                delta[idx] += sign * contrib;
                // cout << "j: " << j << ", contrib: " << contrib << ", idx: " << idx << "\n";
            }
        }
        // if (!rights[i].empty()) {cout << "rights:\n";}
        for (auto [l, r, sign, idx]: rights[i]) {
            lep(j,l+1,r) {
                int num_less = query_num_less(a[j]);
                int num_greater = query_num_greater(a[j]);
                int sum_less = query_sum_less(a[j]);
                int sum_greater = query_sum_greater(a[j]);
                int contrib = vals[a[j]] * num_less - sum_less + sum_greater - vals[a[j]] * num_greater;
                // cout << "j: " << j << ", contrib: " << contrib << ", idx: " << idx << "\n";
                // cout << "j:\n";
                // cout << "num_less: " << num_less << ", num_greater: " << num_greater << ", sum_less: " << sum_less << ", sum_greater: " << sum_greater << ", val: " << vals[a[j]] << ", a[j]: " << a[j] << "\n";
                delta[idx] += sign * contrib;
            }
        }
        // cout << "\n";
    }
    // cout << les[0] << " " << lazy_les[0] << "\n";

    vector<vector<int>> query_answers(q+1);
    int cur_ans = 0;
    for (auto [l,r,idx]: queries) {
        int actual_index = (idx + 3) / 4;
        cur_ans += delta[idx];
        // cout << "l: " << l << ", r: " << r << ", idx: " << idx << ", cur_ans: " << cur_ans << "\n";
        // cout << "delta: " << delta[idx] << "\n";
        query_answers[actual_index].pb(cur_ans);
    }
    lep(qq,1,q) {
        sort(query_answers[qq].begin(), query_answers[qq].end());
        assert((int)query_answers[qq].size() == 4);
        auto &x = query_answers[qq];
        // cout << "x: \n";
        // for (int y: x) {
        //     cout << y << " ";
        // }
        // cout << "\n";
        int ans = x[3] - x[2] - x[1] + x[0];
        cout << ans << "\n";
    }

/*
2 1
1 2
1 1 2 2
*/

/*
3 1
1 2 3    
1 2 2 3
l: 2, r: 3, idx: 1, cur_ans: 10
delta: 10
l: 0, r: 3, idx: 3, cur_ans: 5
delta: -5
l: 1, r: 2, idx: 2, cur_ans: 4
delta: -1
l: 0, r: 1, idx: 4, cur_ans: 4
delta: 0
5

should be
- (2,3) -> 5
- (0,3) -> 0
- (1,2) -> 1
- (0, 1) -> 0
resulting in 4
*/


    
} 

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/