#include <bits/stdc++.h>
 
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
 
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int BLOCK = 350;

int n, q;
int a[MAXN], b[MAXN];
pii compress[MAXN];
int diff[4 * MAXN];
int ans[MAXN];
int l = 1, r = 1, totans;
int qcnt = 0;
int bl[MAXN], br[MAXN], which[MAXN];
int innercnt[MAXN], innerpsum[MAXN];
int blockcnt[MAXN], blockpsum[MAXN];


struct Query {
    int l, r, i, type;
};

Query queries[4 * MAXN];
vector<Query> ops[MAXN];

bool comp(Query a, Query b) {
    if((a.l / BLOCK) == (b.l / BLOCK)) {
        return a.r < b.r;
    }
    return (a.l / BLOCK) < (b.l / BLOCK);
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);

	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
        cin >> a[i]; compress[i] = {a[i], i};
    }

    sort(compress + 1, compress + 1 + n);

    int val = 1;
    for(int i = 1; i <= n; ++i) {
        if(i > 1 && compress[i - 1].ff != compress[i].ff) ++val;
        b[compress[i].ss] = val;
    }

    for(int i = 1; i <= q; ++i) {
        int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        queries[++qcnt] = {r1, r2, i, 1};
        if(l1 > 1) queries[++qcnt] = {l1 - 1, r2, i, -1};
        if(l2 > 1) queries[++qcnt] = {r1, l2 - 1, i, -1};
        if(l1 > 1 && l2 > 1) queries[++qcnt] = {l1 - 1, l2 - 1, i, 1};
    }
    
    sort(queries + 1, queries + 1 + qcnt, comp);

    for(int i = 1; i <= qcnt; ++i) {
        diff[i] = 0;

        // cout << queries[i].l << " " << queries[i].r << " " << queries[i].i << " " << queries[i].type << endl;

        // cout << "hello" << endl;

        if(queries[i].r > r) ops[l].push_back({r + 1, queries[i].r, i, 1});
        if(queries[i].r < r) ops[l].push_back({queries[i].r + 1, r, i, -1});   // pointer will move from qry r + 1 to r 
        if(queries[i].l > l) ops[queries[i].r].push_back({l + 1, queries[i].l, i, 1});
        if(queries[i].l < l) ops[queries[i].r].push_back({queries[i].l + 1, l, i, -1});

        l = queries[i].l; r = queries[i].r;
        // cout << l << " " << r << endl;
    }

    int bucket = (n - 1) / BLOCK + 1;

    for(int i = 1; i <= bucket; ++i) {
        bl[i] = br[i - 1] + 1;
        br[i] = br[i - 1] + BLOCK;
    }
    br[bucket] = n;

    for(int i = 1; i <= bucket; ++i) {
        for(int j = bl[i]; j <= br[i]; ++j) which[j] = i;
    }

    // for(int i = 1; i <= n; ++i) {
    //     cout << bl[which[i]] << " " << br[which[i]] << endl;
    // }

    // for(int i = 1; i <= n; ++i) {
    //     cout << a[i] << " " << b[i] << endl;
    // }

    // for(int i = 1; i <= n; ++i) {
    //     cout << i << ": ";
    //     for(auto qry : ops[i]) {
    //         cout << "(" << qry.l << "," << qry.r << "," << qry.i << "," << qry.type << ")";
    //     }
    //     cout << endl;
    // }

    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = which[b[i]] + 1; j <= bucket; ++j) {
            // cout << "hello" << endl;
            ++blockcnt[j]; blockpsum[j] += a[i];
        }
        for(int j = b[i]; j <= br[which[b[i]]]; ++j) {
            ++innercnt[j]; innerpsum[j] += a[i];
        }

        sum += a[i];
        // cout << "sum: " << sum << endl;

        for(auto qry : ops[i]) {
            for(int j = qry.l; j <= qry.r; ++j) {
                // cout << a[j] << " " << (2 * (innercnt[b[j]] + blockcnt[which[b[j]] + 1]) - i) << " " << sum << " " << -2 * (innerpsum[b[j]] + blockpsum[which[b[j]] + 1]) << endl;
                diff[qry.i] += qry.type * (a[j] * (2 * (innercnt[b[j] - 1] + blockcnt[which[b[j] - 1]]) - i) + sum - 2 * (innerpsum[b[j] - 1] + blockpsum[which[b[j] - 1]]));
                // cout << qry.type << " " << diff[qry.i] << endl;
            }
        }
    }

    for(int i = 1; i <= qcnt; ++i) {
        diff[i] += diff[i - 1];
        ans[queries[i].i] += queries[i].type * diff[i];
    }

    for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return 0;
}