#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
const int T=1e3+5;
int n,m,s,sv,len;
int a[N];
struct sdf{
    int l,r,a,b,id;
}q[M];
int L[T],R[T],pos[N];
int ans1[M],ans2[M];
int tag1[T]={0},num[N]={0};
int tag2[T]={0};
bool cmp(sdf x,sdf y){
    if (x.l/s!=y.l/s)return x.l<y.l;
    if ((x.l/s)&1)return x.r<y.r;
    else return x.r>y.r;
}
void add(int x){
    x=a[x];
    if (num[x]==0)tag2[pos[x]]++;
    num[x]++;tag1[pos[x]]++;
    return ;
}
void del(int x){
    x=a[x];
    num[x]--;tag1[pos[x]]--;
    if (num[x]==0)tag2[pos[x]]--;
    return ;
}
int ask1(int a,int b){
    int posa=pos[a],posb=pos[b],ans=0;
    if (posa==posb){
        for (int i=a;i<=b;i++)ans+=num[i];
        return ans;
    } 
    for (int i=a;i<=R[posa];i++)ans+=num[i];
    for (int i=posa+1;i<=posb-1;i++)ans+=tag1[i];
    for (int i=L[posb];i<=b;i++)ans+=num[i];
    return ans;
}
int ask2(int a,int b){
    int posa=pos[a],posb=pos[b],ans=0;
    if (posa==posb){
        for (int i=a;i<=b;i++)ans+=(num[i]!=0);
        return ans;
    }
    for (int i=a;i<=R[posa];i++)ans+=(num[i]!=0);
    for (int i=posa+1;i<=posb-1;i++)ans+=tag2[i];
    for (int i=L[posb];i<=b;i++)ans+=(num[i]!=0);
    return ans;
}
int main(){
    freopen ("ahoi2013_homework.in","r",stdin);
    freopen ("ahoi2013_homework.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)scanf("%d",&a[i]);
    for (int i=1;i<=m;i++){
        scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b);q[i].id=i;
    }
    s=max(1.0,n/sqrt(m));
    sort(q+1,q+m+1,cmp);
    sv=sqrt(1e5),len=1e5/sv;
    for (int i=1;i<=sv;i++){
        L[i]=(i-1)*len+1;R[i]=i*len;
    }
    if (R[sv]<1e5){
        sv++;L[sv]=R[sv-1]+1;R[sv]=1e5;
    }
    for (int i=1;i<=sv;i++){
        for (int j=L[i];j<=R[i];j++)pos[j]=i;
    }
    int nowl=1,nowr=0;
    for (int i=1;i<=m;i++){
        while(nowl<q[i].l)del(nowl++);
        while(nowl>q[i].l)add(--nowl);
        while(nowr<q[i].r)add(++nowr);
        while(nowr>q[i].r)del(nowr--);
        ans1[q[i].id]=ask1(q[i].a,q[i].b);
        ans2[q[i].id]=ask2(q[i].a,q[i].b);
    }
    for (int i=1;i<=m;i++){
        printf("%d %d\n",ans1[i],ans2[i]);
    }
    return 0;
}