#include<bits/stdc++.h>
#define blo_lr blo
using namespace std;
int Ans1=0,block,Ans2=0,l,r,a,b,n,m,block_ab,mmax=-1;//Ans1表示数字种数,Ans2表示总和 
int aa[114514],vis[114514],blo[114514],A1[114514],A2[114514];
struct node{
	int l,r,a,b,id;
}q[114514];
inline void out(int aaa){
	if (aaa>=10) out(aaa/10);
	putchar(aaa%10+'0');
}
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-'0';
		ch=getchar();
	}
	return x*f;
}
bool cmp1_ab(node a1,node a2){
	if (blo[a1.a]==blo[a2.a]) return a1.b<a2.b;
	return blo[a1.a]<blo[a2.a];
}
bool cmp1_lr(node a1,node a2){
	if (blo_lr[a1.l]==blo_lr[a2.l]) return a1.r<a2.r;
	return blo_lr[a1.l]<blo_lr[a2.l];
}
bool cmp2_lr(node a1,node a2){
	if (blo[a1.l]!=blo[a2.l]) return a1.l<a2.l;
	if(!(blo[a1.l]%2))return a1.r>a2.r;
	return blo_lr[a1.l]<blo_lr[a2.l];
}
void add_lr(int x){
	vis[aa[x]]++;
	if (aa[x]>=a&&aa[x]<=b){
		Ans2++;
		if (vis[aa[x]]==1) Ans1++;
	} 
}
void del_lr(int x){
	vis[aa[x]]--;
	if (aa[x]>=a&&aa[x]<=b){
		Ans2--;
		if (vis[aa[x]]==0) Ans1--;
	} 
}
void add_ab(int x){
	if (vis[x]>=1)
	{
		Ans1++;
		Ans2+=vis[x];
	}
}
void del_ab(int x){
	if (vis[x]>=1){
		Ans1--;
		Ans2-=vis[x];
	}
}
int main (){
	n=read(),m=read();
	block=sqrt(n)*m;
	for (int i = 1;i <= n;i++){blo_lr[i]=(i-1)/block+1;}
	for (int i = 1;i <= n;i++){aa[i]=read();if(aa[i]>mmax){mmax=aa[i];}}
	block_ab=sqrt(mmax)*m;
	for (int i = 1;i <= mmax;i++){blo[i]=(i-1)/block+1;}
	for (int i = 1;i <= m;i++){
		q[i].l=read();q[i].r=read();q[i].a=read();q[i].b=read();
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp2_lr);
	l=1;r=0;a=1;b=0;
	for (int i = 1;i <= m;i++)
	{
		if (q[i].a>q[i].b||q[i].l>q[i].r)
		{
			A1[q[i].id]=A2[q[i].id]=0;
			continue;
		}
		while (l < q[i].l) del_lr(l++);
		while (l > q[i].l) add_lr(--l);
		while (r < q[i].r) add_lr(++r);
		while (r > q[i].r) del_lr(r--);
		while (a > q[i].a) add_ab(--a);
		while (a < q[i].a) del_ab(a++);
		while (b > q[i].b) del_ab(b--);
		while (b < q[i].b) add_ab(++b);
		A1[q[i].id]=Ans2;
		A2[q[i].id]=Ans1;
	}
	for (int i = 1;i <= m;i++)
	{
		out(A1[i]);
		putchar(' ');
		out(A2[i]);
		putchar('\n');
	}
	return 0;
}