#include <bits/stdc++.h>
#define maxn 1000100
using namespace std;
namespace IO {
	char *p1, *p2, buf[15000];
	//#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,15000,stdin),p1==p2)?EOF:*p1++)
#define nc() getchar()
	inline int read() {
		int x = 0, f = 1;
		char ch = nc();
		while (ch < 48 || ch > 57) {
			if (ch == '-')
				f = -1;
			ch = nc();
		}
		while (ch >= 48 && ch <= 57)
			x = (x << 1) + (x << 3) + (ch ^ 48),
			ch = nc();
		return x * f;
	}
	inline void write(int x) {
		if (x < 0)
			putchar('-'), x = -x;
		if (x > 9)
			write(x / 10);
		putchar(x % 10 + '0');
		puts("");
		return;
	}
}
using IO::read;
using IO::write;
int blo;
int bl[maxn], c[maxn] = {0}; //分块所需
struct node { //莫队所需
	int ql, qr, qa, qb, qi;
} q[maxn];
inline bool cmp(node a, node b) {
	return (bl[a.ql] == bl[b.ql]) ? a.qr < b.qr : bl[a.ql] < bl[b.ql];
}
int cnt[10010]; //统计每块出现次数
int n, m;
int a[maxn]; //
inline void add(int x) {
	if (++c[x] == 1)
		cnt[bl[x]]++;
}
inline void suc(int x) {
	if (--c[x] == 0)
		cnt[bl[x]]--;
}
//看看能不能搞一把指针优化 update md不搞了，搞错值域分块的基础了，搞不来
//因为这玩意不是说直接加个ans，是要根据分块搞的

inline int ask(int l, int r) {
	if(l > r) return 0;
	int res = 0;
	if (bl[l] == bl[r])
		for (int i = l; i <= r; i++) res += (c[i] > 0);
	else {
		for (int i = l; i <= blo * bl[l]; i++) res += (c[i] > 0);
		for (int i = (bl[r] - 1) * blo + 1; i <= r; i++) res += (c[i] > 0);
	}
	for (int i = bl[l] + 1; i <= bl[r] - 1; i++) res += cnt[i];
	return res;
}

inline int ask2(int l, int r) {
	if(l > r) return 0;
	int res = 0;
	for (int i = l; i <= min(bl[l] * blo, r); i++) res += c[i];
	if (bl[l] != bl[r])
		for (int i = (bl[r] - 1) * blo + 1; i <= r; i++) res += c[i];
	for (int i = bl[l] + 1; i <= bl[r] - 1; i++) res += cnt[i];
	return res;
}

int ans[maxn];
int ans2[maxn];
int main() {
//	freopen("2.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	n = read(), m = read();
	blo = sqrt(1e5);
	for (int i = 1; i <= n; i++) a[i] = read(), bl[i] = (i - 1) / blo + 1;
	for (int i = 1; i <= m; i++)
		q[i].ql = read(), q[i].qr = read(), q[i].qa = read(), q[i].qb = read(), q[i].qi = i;
	sort(q + 1, q + 1 + m, cmp);
	int nowl = 1, nowr = 0;
	for (int i = 1; i <= m; i++) {
		int ql = q[i].ql, qr = q[i].qr, qi = q[i].qi;
		while (nowl < ql) suc(a[nowl++]);
		while (nowl > ql) add(a[--nowl]);
		while (nowr < qr) add(a[++nowr]);
		while (nowr > qr) suc(a[nowr--]);
		ans[qi] = ask(q[i].qa, q[i].qb);
		ans2[qi] = ask2(q[i].qa, q[i].qb);
	}
	for (int i = 1; i <= m; i++) printf("%d %d\n", ans2[i], ans[i]);
	return 0;
}