如下：

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)? EOF : *p1++)
struct FastIO
{
    inline FastIO& operator >> (int& x) {
        x = 0; char f = 0, ch = getchar();
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (long long& x) {
        x = 0; char f = 0, ch = getchar();
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (double& x) {
        x = 0; char f = 0, ch = getchar();
        double d = 0.1;
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x=x * 10 + ch - 48, ch = getchar();
        if(ch == '.')
        {
            ch = getchar();
            while(ch <= '9' && ch >= '0') x += d * (ch ^ 48), d *= 0.1, ch = getchar();
        }
        return x = (f ? -x : x), *this;
    }
}rin;
inline void qWrite(const int x) {
	if (x > 9) qWrite(x / 10);
	putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
int n, m, a[N], b[N];
pair<int, int> ansQ[N];
struct Query {
	int id, l, r, ql, qr, blockID;
}q[N];
bool cmp(const Query& qA, const Query& qB) {
	if (qA.blockID != qB.blockID) return qA.blockID < qB.blockID;
	if (qA.blockID & 1) return qA.r < qB.r;
	return qA.r > qB.r;
}
int sum[N << 2], cnt[N << 2];
inline void pushup(int p) {
	sum[p] = sum[p << 1] + sum[p << 1 | 1];
	cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
}
inline void add(int p, int l, int r, const int& id) {
	if (l == r) {
		++sum[p], cnt[p] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (id <= mid) add(p << 1, l, mid, id);
	else add(p << 1 | 1, mid + 1, r, id);
	pushup(p);
}
inline void add(const int& id) {
	add(1, 1, 1e5, id);
}
inline void del(int p, int l, int r, const int& id) {
	if (l == r) {
		if (!(--sum[p])) cnt[p] = 0;
		return;
	}
	int mid = (l + r) >> 1;
	if (id <= mid) del(p << 1, l, mid, id);
	else del(p << 1 | 1, mid + 1, r, id);
	pushup(p);
}
inline void del(const int& id) {
	del(1, 1, 1e5, id);
}
inline void operator +=(pair<int, int>& p1, pair<int, int> p2) {
	p1.first += p2.first, p1.second += p2.second;
}
inline pair<int, int> query(int p, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return make_pair(sum[p], cnt[p]); 
	int mid = (l + r) >> 1;
	pair<int, int> ans = make_pair(0, 0);
	if (ql <= mid) ans += query(p << 1, l, mid, ql, qr);
	if (qr > mid) ans += query(p << 1 | 1, mid + 1, r, ql, qr);
	return ans;
} 
signed main() {
	ios :: sync_with_stdio(false);
	rin >> n >> m;
	const int B = 75;
	for (int i = 1; i <= n; ++i) b[i] = (i - 1) / B + 1;
	for (int i = 1; i <= n; ++i) rin >> a[i];
	for (int i = 1; i <= m; ++i) {
		q[i].id = i;
		rin >> q[i].l >> q[i].r >> q[i].ql >> q[i].qr;
		q[i].blockID = b[q[i].l];
	}
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;	
	for (int i = 1; i <= m; ++i) {
		while (r < q[i].r) add(a[++r]);
		while (l > q[i].l) add(a[--l]);
		while (r > q[i].r) del(a[r--]);
		while (l < q[i].l) del(a[l++]);
		ansQ[q[i].id] = query(1, 1, 1e5, q[i].ql, q[i].qr);
	}
	for (int i = 1; i <= m; ++i) {
		qWrite(ansQ[i].first);
		putchar(' ');
		qWrite(ansQ[i].second);
		putchar('\n'); 
	}
	return 0;
}