#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
	while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
	return x * f;
}
const int N = 1e5 + 5, M = 34000;
struct Que {
	int l, r, num;
} q[M * 3 + 5];
struct Node {
	int data, num;
	inline bool operator < (const Node &x) const {
		return data < x.data;
	}
} h[N];
bitset <N> ans[M + 5], w;
int n, m, tot;
int a[N], cnt[N], sum[M + 5];
unordered_map <int, int> b;
inline bool cmp1(Que c, Que d) {
	return c.l < d.l;
}
inline bool cmp2(Que c, Que d) {
	return c.r > d.r;
}
inline void add(int x) {
	w[x - cnt[x]] = 1; cnt[x]++;
}
inline void del(int x) {
	cnt[x]--; w[x - cnt[x]] = 0;
}
inline void solve() {
	if (tot >= m) return;
	int num = 0;
	for (int i = 1; i <= M && tot < m; i++) {
		++tot; sum[i] = 0;
		q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1;
		q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1;
		q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1;
	}
	for (int i = 1; i <= num / 3; i++) ans[i].set();
	int step = sqrt(num);
	sort(q + 1, q + num + 1, cmp1);
	for (int i = 1; i <= num; i += step) {
		int l = i, r = min(i + step - 1, num);
		sort(q + l, q + r + 1, cmp2);
	}
	int L = 1, R = 0;
	for (int i = 1; i <= num; i++) {
		if (R < q[i].l || L > q[i].r) {
			for (int j = L; j <= R; j++) del(a[j]);
			L = q[i].l; R = q[i].r;
			for (int j = L; j <= R; j++) add(a[j]);
		}
		else {
			while (R < q[i].r) add(a[++R]);
			while (R > q[i].r) del(a[R--]);
			while (L < q[i].l) del(a[L++]);
			while (L > q[i].l) add(a[--L]);
		}
		ans[q[i].num] &= w;
	}
	for (int i = L; i <= R; i++) del(a[i]);
	for (int i = 1; i <= num / 3; i++) printf("%d\n", sum[i] - 3 * ans[i].count());
}
int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		h[i].data = read();
		b[h[i].data]++;
		h[i].num = i;
	}
	sort(h + 1, h + n + 1);
	int pre = 0, s = 0;
	for (int i = 1; i <= n; i++) {
		if (h[i].data == pre) a[h[i].num] = s;
		else {
			s += b[h[i].data];
			pre = h[i].data;
			a[h[i].num] = s;
		}
	}
	solve(); solve(); solve();
	return 0;
}