代码如下：

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 100005
#define M 1000500
using namespace std;
int n,m,a[N],len,ans[M][2],len2,mx,P[N];
struct node{
	int l,r,a,b,p,id;
}in[M];
int mp[N],sum[N],sum2[N];
void del(int x) {
	mp[x] --;
	sum[P[x]] --;
	if (mp[x] == 0) sum2[P[x]] --;
}
void add(int x) {
	mp[x] ++;
	sum[P[x]] ++;
	if (mp[x] == 1) sum2[P[x]] ++;
}
void getans(int a,int b,int id) {
	if (P[a] == P[b]) {
		for (int i = a;i <= b;i ++) ans[id][0] += mp[i],ans[id][1] += mp[i] > 0;
		return;
	}
	for (int i = a;P[i] == P[a];i ++) ans[id][0] += mp[i],ans[id][1] += mp[i] > 0;
	for (int i = P[a] + 1;i < P[b];i ++) ans[id][0] += sum[i],ans[id][1] += sum2[i];
	for (int i = b;P[i] == P[b];i --) ans[id][0] += mp[i],ans[id][1] += mp[i] > 0;
}
//void getans(int a,int b,int id) {
//	int res = 0;
////	for (int i = a;i <= b;i ++)
////		res += mp[i];
//	while(a % len2 != 0 && b > a) res += mp[a],ans[id][1] += mp[a] > 0,a ++;
//	while(b % len2 != 0 && b > a) res += mp[b],ans[id][1] += mp[b] > 0,b --;
//	if (a == b && b % len2 != 0) res += mp[b],ans[id][1] += mp[b] > 0;
//	if (b >= a && b % len2 == 0) res += mp[b],ans[id][1] += mp[b] > 0;
//	for (int i = a / len2;i < b / len2;i ++) res += sum[i],ans[id][1] += sum2[i];
//	ans[id][0] = res;
//}
//int getres(int a,int b) {
//	int res = 0;
////	for (int i = a;i <= b;i ++)
////		res += (mp[i] > 0);
//	while(a % len2 != 0 && b > a) res += mp[a] > 0,a ++;
//	while(b % len2 != 0 && b > a) res += mp[b] > 0,b --;
//	if (a == b && b % len2 != 0) res += mp[b] > 0;
//	if (b >= a && b % len2 == 0) res += mp[b] > 0;
//	for (int i = a / len2;i < b / len2;i ++) res += sum2[i];
//	return res;
//}
signed main() {
	cin >> n >> m;
	for (int i = 1;i <= n;i ++) scanf("%d",&a[i]),mx = max(mx,a[i]);
	len = n / sqrt(m);
	len2 = sqrt(mx);
	if (len == 0) len ++;
	for (int i = 1;i <= 1e5;i ++) P[i] = i / len2;
	for (int i = 1;i <= m;i ++) {
		in[i].id = i;
		scanf("%d%d%d%d",&in[i].l,&in[i].r,&in[i].a,&in[i].b);
		in[i].p = P[in[i].id];
	}
	stable_sort(in + 1,in + 1 + m,[](node x,node y) {
		if (x.p == y.p) return (x.p & 1 ? x.r > y.r : x.r < y.r);
		return x.p < y.p;
	});
	int l = 1,r = 0;
	for (int i = 1,ql,qr;i <= m;i ++) {
		ql = in[i].l,qr = in[i].r;
		while(ql < l) add(a[--l]);
		while(ql > l) del(a[l++]);
		while(qr > r) add(a[++r]);
		while(qr < r) del(a[r--]);
		getans(in[i].a,in[i].b,in[i].id); 
	}
	for (int i = 1;i <= m;i ++) printf("%d %d\n",ans[i][0],ans[i][1]);
	return 0;
}