#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 100005struct QueryType {    int l,r,a,b,id;};struct QueryType qu[maxn*10];int n,sum[maxn],sum_[maxn],ti[maxn],ans[maxn*10][2];int ai[maxn],size,bel[maxn],m;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>‘9‘||Cget<‘0‘) Cget=getchar();    while(Cget>=‘0‘&&Cget<=‘9‘)    {        now=now*10+Cget-‘0‘;        Cget=getchar();    }}inline int lowbit(int x){    return x&(-x);}inline void sadd(int x,int k){    while(x<=n) sum[x]+=k,x+=lowbit(x);}inline int ssum(int p,int x){    int res=0;p--;    while(x) res+=sum[x],x-=lowbit(x);    while(p) res-=sum[p],p-=lowbit(p);    return res;}inline void tadd(int x,int k){    while(x<=n) sum_[x]+=k,x+=lowbit(x);}inline int tsum(int p,int x){    int res=0;p--;    while(x) res+=sum_[x],x-=lowbit(x);    while(p) res-=sum_[p],p-=lowbit(p);    return res;}inline bool cmp(QueryType aaa,QueryType bbb){    if(bel[aaa.l]==bel[bbb.l])    {        if(bel[aaa.r]==bel[bbb.r])        {            if(aaa.l==bbb.l) return aaa.r<bbb.r;            else return aaa.l<bbb.l;        }        return bel[aaa.r]<bel[bbb.r];    }    else return bel[aaa.l]<bel[bbb.l];}inline void updata(int now,int x){    int pre=ti[now];    ti[now]+=x,sadd(now,x);    if(pre==0&&ti[now]==1) tadd(now,1);    if(pre==1&&ti[now]==0) tadd(now,-1);}int main(){    in(n),in(m),size=sqrt(n);for(int i=1;i<=n;i++) in(ai[i]),bel[i]=(i-1)/size;    for(int i=1;i<=m;i++) in(qu[i].l),in(qu[i].r),in(qu[i].a),in(qu[i].b),qu[i].id=i;    sort(qu+1,qu+m+1,cmp);int l=1,r=0,pos;    for(int no=1;no<=m;no++)    {        if(l<qu[no].l) for(int i=l;i<qu[no].l;i++) updata(ai[i],-1);        else for(int i=l-1;i>=qu[no].l;i--) updata(ai[i],1);        if(r>qu[no].r) for(int i=r;i>qu[no].r;i--) updata(ai[i],-1);        else for(int i=r+1;i<=qu[no].r;i++) updata(ai[i],1);        l=qu[no].l,r=qu[no].r,ans[qu[no].id][1]=ssum(qu[no].a,qu[no].b),ans[qu[no].id][2]=tsum(qu[no].a,qu[no].b);    }    for(int i=1;i<=m;i++) printf("%d %d\n",ans[i][1],ans[i][2]);    return 0;}