#include<bits/stdc++.h>
using namespace std;
int n,m,q,ksize;
int blk[100001];
int st[321],ed[321];
int a[100001];
namespace IN {
    const int MAX_IN = 1000000;
    #define getc() (p1 == p2 && (p2 = (p1 = buf) + inbuf -> sgetn(buf, MAX_INPUT), p1 == p2) ? EOF : *p1++)
    char buf[MAX_IN], *p1, *p2;
    template <typename T> inline bool redi(T &x) {
        static streambuf *inbuf = cin.rdbuf();
        x = 0;
        register int f = 0, flag = false;
        register char ch = getc();
        while (!isdigit(ch)) {
            if (ch == '-') f = 1;
        ch = getc();
        }
        if (isdigit(ch)) x = x * 10 + ch - '0', ch = getc(),flag = true;
        while (isdigit(ch)) {
            x = x * 10 + ch - 48;
            ch = getc();
        }
        x = f ? -x : x ;
        return flag;
    }
    template <typename T,typename ...Args> inline bool redi(T& a,Args& ...args) {
       return redi(a) && redi(args...);
    }
    #undef getc
}
struct{
	int xian;
	int hou;
	void write(){
		printf("%d %d\n",xian,hou);
	}
}ans[100001];
int cnt[100001][2];
int bel[100001];
int kuaisum[321][2];
struct kuai{
	int l;
	int r;
	int a;
	int b;
	int id;
	bool operator <(const kuai& a)const{
		if(blk[l]==blk[a.l])
			if(blk[l]&1) return r<a.r;
			else return r>a.r;
		else
			return l<a.l;
	}
}ask[100001]; 
inline void add(int wei){
	cnt[a[wei]][0]++,kuaisum[bel[a[wei]]][0]++;
	if(cnt[a[wei]][0]==1)
		cnt[a[wei]][1]++,kuaisum[bel[a[wei]]][1]++;
}
inline void sub(int wei){
	cnt[a[wei]][0]--,kuaisum[bel[a[wei]]][0]--;
	if(cnt[a[wei]][0]==0)
		cnt[a[wei]][1]--,kuaisum[bel[a[wei]]][1]--;
}
void query(int id,int La,int Lb){
	register int ans1=0,ans2=0;
	if(bel[La]==bel[Lb]){
		for(register int i=La;i<=Lb;i++)
			ans1+=cnt[i][0],ans2+=cnt[i][1];
	}
	else{
		for(register int i=bel[La]+1;i<bel[Lb];i++)
			ans1+=kuaisum[i][0],ans2+=kuaisum[i][1];
		for(register int i=La;i<=ed[bel[La]];i++)
			ans1+=cnt[i][0],ans2+=cnt[i][1];
		for(register int i=st[bel[Lb]];i<=Lb;i++)
			ans1+=cnt[i][0],ans2+=cnt[i][1];
	}
	ans[id].xian=ans1,ans[id].hou=ans2;
}
signed main(){
	IN::redi(n,m);q=sqrt(n);ksize=317;
	for(register int i=1;i<=ksize;i++)
		st[i]=100000/ksize*(i-1)+1,ed[i]=100000/ksize*i;ed[ksize]=100000;
	for(register int i=1;i<=ksize;i++)
		for(register int j=st[i];j<=ed[i];j++)
			bel[j]=i;
	for(register int i=1;i<=n;i++)
		IN::redi(a[i]),blk[i]=n/q+1;
	for(register int i=1;i<=m;i++){
		IN::redi(ask[i].l,ask[i].r,ask[i].a,ask[i].b);
		ask[i].id=i;
	}
	sort(ask+1,ask+1+m);
	register int l=1,r=0;
	for(register int i=1;i<=m;i++){
		register int linl=ask[i].l,linr=ask[i].r;
		while(l>linl) add(--l);
		while(r<linr) add(++r);
		while(l<linl) sub(l++);
		while(r>linr) sub(r--);
		query(ask[i].id,ask[i].a,ask[i].b);
	}
	for(register int i=1;i<=m;i++)
		ans[i].write();
	return 0;
}