#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

struct QueryType {

    int l,r,a,b,id;

};

struct QueryType qu[maxn*];

int n,sum[maxn],sum_[maxn],ti[maxn],ans[maxn*][];

int ai[maxn],size,bel[maxn],m;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        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=;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=;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==&&ti[now]==) tadd(now,);

    if(pre==&&ti[now]==) tadd(now,-);

}

int main()

{

    in(n),in(m),size=sqrt(n);for(int i=;i<=n;i++) in(ai[i]),bel[i]=(i-)/size;

    for(int i=;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+,qu+m+,cmp);int l=,r=,pos;

    for(int no=;no<=m;no++)

    {

        if(l<qu[no].l) for(int i=l;i<qu[no].l;i++) updata(ai[i],-);

        else for(int i=l-;i>=qu[no].l;i--) updata(ai[i],);

        if(r>qu[no].r) for(int i=r;i>qu[no].r;i--) updata(ai[i],-);

        else for(int i=r+;i<=qu[no].r;i++) updata(ai[i],);

        l=qu[no].l,r=qu[no].r,ans[qu[no].id][]=ssum(qu[no].a,qu[no].b),ans[qu[no].id][]=tsum(qu[no].a,qu[no].b);

    }

    for(int i=;i<=m;i++) printf("%d %d\n",ans[i][],ans[i][]);

    return ;

}