#include<bits/stdc++.h>

using namespace std;

#define Reimu inline void // 灵梦赛高
#define Marisa inline int // 魔理沙赛高

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> Pii;
#define fi first
#define se second

namespace FastInput {
	template<typename Ty>
	Reimu read(Ty &x) { // 默认读入整型 int, LL, Uint, ULL, ...
		x = 0;
		int f = 0;
		char c = getchar();
		for (; !isdigit(c); c = getchar()) f |= c == '-';
		for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
		if (f) x = -x;
	}

	template<>
	Reimu read(double &x) { // 读入浮点型 double
		x = 0;
		int f = 0;
		char c = getchar();
		for (; !isdigit(c); c = getchar()) f |= c == '-';
		for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
		if (c == '.') {
			double e = 1;
			for (c = getchar(); isdigit(c); c = getchar()) x += (c ^ 48) * (e *= .1);
		}
		if (f) x = -x;
	}

	template<>
	Reimu read(char &c) { // 读入字符 char
		do c = getchar(); while (!isgraph(c));
	}

	template<>
	Reimu read(string &s) { // 读入字符串 string
		s = "";
		char c = getchar();
		while (!isgraph(c)) c = getchar();
		for (; isgraph(c); c = getchar()) s += c;
	}

	template<typename Ty, typename...Args>
	Reimu read(Ty &x, Args &...args) { // 不定长传参
		read(x);
		read(args...);
	}
}
using namespace FastInput; // 使用快读

const int N = 100010;

struct Que { int l, r, L, R, k; } q[N];

int n, m, mx;
int a[N], ans1[N], ans2[N];

struct Block {
	static const int M = 350;
	int len, cnt;
	int bel[N], L[M], R[M], s[M], apr[N], c[M];
	Reimu init(int n) {
		len = sqrt(n); cnt = (n - 1) / len + 1;
		for (int i = 1; i <= cnt; ++i) {
			L[i] = R[i - 1] + 1;
			R[i] = i == cnt ? n : len * i;
			for (int j = L[i]; j <= R[i]; ++j) bel[j] = i;
		}
	}
	Reimu add(int x) {
		++s[bel[x]];
		c[bel[x]] += !apr[x]++;
	}
	Reimu del(int x) {
		--s[bel[x]];
		c[bel[x]] -= !--apr[x];
	}
	Marisa query1(int l, int r) {
		int ans = 0;
		for (int i = bel[l] + 1; i < bel[r]; ++i) ans += s[i];
		for (int i = l; i <= min(r, R[bel[l]]); ++i) ans += apr[i];
		if (bel[l] != bel[r]) for (int i = L[bel[r]]; i <= r; ++i) ans += apr[i];
		return ans;
	}
	Marisa query2(int l, int r) {
		int ans = 0;
		for (int i = bel[l] + 1; i < bel[r]; ++i) ans += c[i];
		for (int i = l; i <= min(r, R[bel[l]]); ++i) ans += apr[i] > 0;
		if (bel[l] != bel[r]) for (int i = L[bel[r]]; i <= r; ++i) ans += apr[i] > 0;
		return ans;
	}
} blk;

Reimu solve() {
	sort(q + 1, q + m + 1, [](Que a, Que b) { return a.l < b.l; });
	function<bool(Que, Que)> cmps[] = {[](Que a, Que b) { return a.r > b.r; }, [](Que a, Que b) { return a.r < b.r; }};
	int len = sqrt(m), cnt = (m - 1) / len + 1;
	for (int i = 1; i <= cnt; ++i) {
		int L = len * (i - 1) + 1, R = i == cnt ? m : len * i;
		sort(q + L, q + R + 1, cmps[i & 1]);
	}
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while (r < q[i].r) blk.add(a[++r]);
		while (l > q[i].l) blk.add(a[--l]);
		while (r > q[i].r) blk.del(a[r--]);
		while (l < q[i].l) blk.del(a[l++]);
		ans1[q[i].k] = blk.query1(q[i].L, q[i].R);
		ans2[q[i].k] = blk.query2(q[i].L, q[i].R);
	}
}

int main() {
	read(n, m);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
		mx = max(mx, a[i]);
	}
	blk.init(mx);
	for (int i = 1, l, r, L, R; i <= m; ++i) {
		read(l, r, L, R);
		q[i] = {l, r, L, min(R, mx), i};
	}
	solve();
	for (int i = 1; i <= m; ++i) printf("%d %d\n", ans1[i], ans2[i]);
	return 0;
}