C++ :

#define MAXN 1000010UL

#include <algorithm>
#include <cstdio>
#include <cmath>

struct Query{
	int id,l,r,a,b;
	inline void in(int pid){id=pid,scanf("%d%d%d%d",&l,&r,&a,&b);return;}
};

Query p[MAXN];

int n,m,L,R,tree[MAXN],blocks,c[MAXN],block[MAXN],Ans[MAXN],Ans2[MAXN],tree2[MAXN],ex[MAXN];

inline bool comp(Query a,Query b){
	return block[a.l]==block[b.l]?(a.r<b.r):(a.l<b.l);
}

inline int lowbit(int x){
	return x&(-x);
}

inline void Update(int val,int add){
	if(add==1){
		ex[val]++;
		if(ex[val]==1) for(int i=val;i<=n;i+=lowbit(i)) tree2[i]+=add;
	}
	else{
		ex[val]--;
		if(!ex[val]) for(int i=val;i<=n;i+=lowbit(i)) tree2[i]+=add;
	}
	for(int i=val;i<=n;i+=lowbit(i)) tree[i]+=add; 
	return;
}

inline int Query(int val){
	if(val<=0) return 0;
	int ans=0;
	for(int i=val;i>0;i-=lowbit(i)) ans+=tree[i];
	return ans;
}

inline int Query2(int val){
	if(val<=0) return 0;
	int ans=0;
	for(int i=val;i>0;i-=lowbit(i)) ans+=tree2[i];
	return ans;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=m;i++) p[i].in(i);
	blocks=(int)sqrt(n+0.5);
	for(int i=1;i<=n;i++) block[i]=(i-1)/blocks;
	std::sort(p+1,p+m+1,comp);
	L=p[1].l;R=p[1].r;
	for(int i=L;i<=R;i++) Update(c[i],1);
	if(p[1].b>=p[1].a) Ans[p[1].id]=Query(p[1].b)-Query(p[1].a-1),Ans2[p[1].id]=Query2(p[1].b)-Query2(p[1].a-1);
	else Ans[p[1].id]=0,Ans2[p[1].id]=0;
	for(int i=2;i<=m;i++){
		while(R<p[i].r) R++,Update(c[R],1);
		while(L>p[i].l) L--,Update(c[L],1);
		while(R>p[i].r) Update(c[R],-1),R--;
		while(L<p[i].l) Update(c[L],-1),L++;
		if(p[i].b>=p[i].a) Ans[p[i].id]=Query(p[i].b)-Query(p[i].a-1),Ans2[p[i].id]=Query2(p[i].b)-Query2(p[i].a-1);
		else Ans[p[i].id]=0,Ans2[p[i].id]=0;
	}
	for(int i=1;i<=m;i++) printf("%d %d\n",Ans[i],Ans2[i]);
	return 0;
}