#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn= 1e5+5;
struct node{
	int l,r,id,qx,qy;
}query[maxn];
int c[4*maxn],Ans1[maxn],Ans2[maxn],a[maxn],c2[4*maxn];
int T,tot,n,m;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

bool cmp(node a,node b){
	if(a.l/T==b.l/T) return a.r<b.r;
	return a.l/T<b.l/T;
}

int lowbit(int x){
	return x & (-x);
}
int sum(int x){
	int res=0;
	while(x){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}

int ask(int x,int y){
	return sum(y)-sum(x-1);
}

int sum2(int x){
	int res=0;
	while(x){
		res+=c2[x];
		x-=lowbit(x);
	}
	return res;
}

int ask2(int x,int y){
	return sum2(y)-sum2(x-1);
}

void add2(int x,int y){
	while(x<=n){
		c2[x]+=y;
		x+=lowbit(x);
	}
}

void add(int x,int y){
	if(ask(x,x)==1&&y==-1){
		add2(x,-1);
	}
	else if(ask(x,x)==0&&y==1){
		
		add2(x,1);
	}
	while(x<=n){
		c[x]+=y;
		x+=lowbit(x);
	}

}

int main(){
	n=read(),m=read();
	int x,y,l,r;
	tot=0;
	T=sqrt(n);
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++){
		l=read(),r=read(),x=read(),y=read();
		query[i].id=i;
		query[i].l=l;
		query[i].r=r;
		query[i].qx=x;
		query[i].qy=y;
	}

	sort(query+1,query+m+1,cmp);
	l=1,r=0;
	for(int i=1;i<=m;i++){
		while(r<query[i].r) add(a[++r],1);
		while(r>query[i].r) add(a[r--],-1);
		while(l>query[i].l) add(a[--l],1);
		while(l<query[i].l) add(a[l++],-1);
		Ans1[query[i].id]=ask(query[i].qx,query[i].qy);
		Ans2[query[i].id]=ask2(query[i].qx,query[i].qy);
	}
	for(int i=1;i<=m;i++){
		cout<<Ans1[i]<<" "<<Ans2[i]<<"\n";
	}
}