#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;

int n, m, a[N];
struct President_Tree {
	int rt[N];
	int cnt[N << 5], ls[N << 5], rs[N << 5], tot;
	int insert(int x, int l, int r, int pos) {
		int y = ++ tot;
		cnt[y] = cnt[x] + 1;
		ls[y] = ls[x];
		rs[y] = rs[x];
		if (l == r) return y;
		int mid = (l + r) >> 1;
		if (pos <= mid) ls[y] = insert(ls[x], l, mid, pos);
		else rs[y] = insert(rs[x], mid + 1, r, pos);
		return y;
	}
	int query(int x, int y, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return cnt[x] - cnt[y];
		}
		int mid = (l + r) >> 1;
		int ans = 0;
		if (ql <= mid) ans += query(ls[x], ls[y], l, mid, ql, qr);
		if (qr > mid) ans += query(rs[x], rs[y], mid + 1, r, ql, qr);
		return ans;
	}
} s;
int b[N], tot;
int block;
int ans1[N], ans2[N], cnt[N];
struct Query {
	int l, r, a, b, id;
	bool operator < (const Query &o) const {
		return l / block ^ o.l / block ? l / block < o.l / block : r < o.r;
	}
} Q[N];
int sum[N << 2]; // SegmentTree
void update(int x, int l, int r, int pos, int val) {
	if (l == r) {
		sum[x] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) update(x << 1, l, mid, pos, val);
	else update(x << 1 | 1, mid + 1, r, pos, val);
	sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
int query(int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		return sum[x];
	}
	int mid = (l + r) >> 1;
	int ans = 0;
	if (ql <= mid) ans += query(x << 1, l, mid, ql, qr);
	if (qr > mid) ans += query(x << 1 | 1, mid + 1, r, ql, qr);
	return ans;
}
void add(int x) {
	if (++ cnt[a[x]] == 1) update(1, 1, 100000, a[x], 1);
}
void del(int x) {
	if (-- cnt[a[x]] == 0) update(1, 1, 100000, a[x], 0);
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);


	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		s.rt[i] = s.insert(s.rt[i - 1], 1, 100000, a[i]);
	}
	block = sqrt(n);

	for (int i = 1; i <= m; ++ i) {
		int l, r, x, y;
		cin >> l >> r >> x >> y;
		Q[i] = {l, r, x, y, i};
	}
	sort(Q + 1, Q + m + 1);

	int L = 1, R = 0;
	for (int i = 1; i <= m; ++ i) {
		auto &[l, r, x, y, id] = Q[i];
		while (L > l) add(-- L);
		while (R < r) add(++ R);
		while (L < l) del(L ++ );
		while (R > r) del(R -- );
		ans1[id] = s.query(s.rt[r], s.rt[l - 1], 1, 100000, x, y);
		ans2[id] = query(1, 1, 100000, x, y);
	}
	for (int i = 1; i <= m; ++ i) {
		cout << ans1[i] << ' ' << ans2[i] << '\n';
	}
	return 0;
}