#include <bits/stdc++.h>

template <int T> 
struct fast_io {
	char p[T], q[T], *p1, *p2, *q1, *q2;
	fast_io() {
		p1 = p2 = p;
		q1 = q, q2 = q + T;
	}	
	char gc() {
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	void pc(char ch) {
		if (q1 == q2) {
			fwrite(q, 1, T, stdout);
			q1 = q;
		}
		*q1++ = ch;
	}
	~fast_io() {
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<1024768> io;

int read() {
	int r = 0, ng = 1;
	char ch;
	do {
		ch = io.gc();
		if (ch == '-') {
			ng = -1;
		}
	} while (!isdigit(ch));
	do r = r * 10 + ch - 48, ch = io.gc(); while (isdigit(ch));
	return r * ng;
}

void write(int64_t x) {
	if (x < 0) x = -x, io.pc('-');
	if (x >= 10)
		write(x / 10);
	io.pc(48 + x % 10);
}

void output(int64_t x, char ch = ' ') {
	write(x);
	io.pc(ch);
}

const int N = 1e5 + 50, B = 316;

struct val_t {
	int64_t sum, cnt;
	val_t () = default;
	val_t (int64_t sum, int64_t cnt) : cnt(cnt), sum(sum) {

	}
	val_t operator+(const val_t &rhs) const {
		return val_t(sum + rhs.sum, cnt + rhs.cnt);
	}
	val_t operator-(const val_t &rhs) const {
		return val_t(sum - rhs.sum, cnt - rhs.cnt);
	}
	val_t& operator+=(const val_t &rhs) {
		cnt += rhs.cnt;
		sum += rhs.sum;
		return *this;
	}
} zero(0, 0);

struct query_t {
	int l, r, id, k;
	query_t(int l, int r, int id, int k) : l(l), r(r), k(k), id(id) {

	}
	bool operator<(const query_t &rhs) const {
		const int o = l / B, ro = rhs.l / B;
		if (o != ro)
			return o < ro;
		if (o & 1)
			return r > rhs.r;
		return r < rhs.r;
	}
};

struct data_structure_t {
	int n, m;
	int64_t total_sum, total_count;
	int left(int x) const { return std::max(0, x * B); }
	int right(int x) const { return std::min(n - 1, x * B + B - 1); }
	val_t bpre[N], pre[N];
	data_structure_t (int n) : n(n) {
		m = n / B;
	}
	void add(int p, int64_t v) {
		total_sum += v;
		total_count += 1;
		int id = p / B;
		val_t y(v, 1);
		for (int j = id + 1; j <= m; ++j) {
			bpre[j] += y;
		}
		for (int j = p; j <= right(id); ++j) {
			pre[j] += y;
		}
	}
	val_t query(int p) const {
		int id = p / B;
		assert(id<=m);
		auto z = bpre[id] + pre[p];
		return z;
	}
};

int main() {
	int n = read(), q = read();
	std::vector<int> a(n), buc(n);
	for (int i = 0; i < n; ++i) {
		buc[i] = a[i] = read();
	}
	{
		std::ranges::sort(buc);
		auto [$1, $2] = std::ranges::unique(buc);
		buc.erase($1, $2);
		std::transform(a.begin(), a.end(), a.begin(), [&](int x) -> int {
			return std::lower_bound(buc.begin(), buc.end(), x) - buc.begin();
		});
	}
	
	std::vector<query_t> queries;
	auto add = [&](int l, int r, int id, int k) {
		if (l >= 0 && r >= 0) {
			queries.emplace_back(l, r, id, k);
		}
		else {
		}
	};
	for (int i = 0; i < q; ++i) {
		int l1 = read(), r1 = read(), l2 = read(), r2 = read();
		--l1, --r1, --l2, --r2;
		add(r1, r2, i, 1);
		add(l1 - 1, r2, i, -1);
		add(r1, l2 - 1, i, -1);
		add(l1 - 1, l2 - 1, i, 1);
	}
	std::sort(queries.begin(), queries.end());
	int L = 0, R = 0;
	std::vector<std::vector<query_t>> events(n, std::vector<query_t>());
	//for (auto [l, r, id, coef] : queries) {
	for (int i = 0; i < queries.size(); ++i) {
		auto [l, r, id, coef] = queries[i];
		if (R < r) {
			events[L].emplace_back(R + 1, r, i, 1);
			R = r;
		}
		if (L > l) {
			events[R].emplace_back(l + 1, L, i, -1);
			L = l;
		}
		if (R > r) {
			events[L].emplace_back(r + 1, R, i, -1);
			R = r;
		}
		if (L < l) {
			events[R].emplace_back(L + 1, l, i, 1);
			L = l;
		}
		assert(L == l && R == r);
	}
	std::vector<int64_t> ans(queries.size()), ret(q);
	data_structure_t T(n);
	auto solve = [&](int64_t v) -> int64_t {
		val_t z = T.query(v);
		int64_t ls = z.sum, lc = z.cnt, rs = T.total_sum - ls, rc = T.total_count - lc;
		int64_t lv = lc * buc[v] - ls;
		int64_t rv = rs - rc * buc[v];
		assert(lv >= 0 && rv >= 0);
		return lv + rv;
	};
	for (int i = 0; i < n; ++i) {
		T.add(a[i], buc[a[i]]);
		for (auto [l, r, id, coef] : events[i]) {
			for (int j = l; j <= r; ++j) {
				ans[id] += coef * solve(a[j]);
			}
		}	
	}
	int64_t cur = 0;
	for (int i = 0; i < queries.size(); ++i) {
		auto [l, r, id, coef] = queries[i];
		cur += ans[i];
		ret[id] += coef * cur;
	}
	for (int i = 0; i < q; ++i) {
		output(ret[i], '\n');
	}
}