#include<bits/stdc++.h>
using namespace std;
#define ls root*2
#define rs root*2+1
struct tre
{
	int l,r,val; 
}t[3][114514*4+1];   //t[1]来存每个数出现的次数，t[2]来存值的个数 
void bld(int l,int r,int root,int id)
{
    t[id][root].l=l;
    t[id][root].r=r;
    if(l==r)
        return;
    int mid=(l+r)/2;
    bld(l,mid,root*2,id);
    bld(mid+1,r,root*2+1,id);
}
void addt(int x,int root,int k,int id)
{
	if(t[id][root].l==t[id][root].r)
	{
		t[id][root].val+=k;
		return;
	}
    int mid=(t[id][root].l+t[id][root].r)/2;
	if(x<=mid)
		addt(x,ls,k,id);
	else
		addt(x,rs,k,id);
	t[id][root].val=t[id][ls].val+t[id][rs].val;
}
int query(int x,int y,int root,int id)
{
    int ret=0;
    if(t[id][root].l>=x&&t[id][root].r<=y)
        return t[id][root].val;
    int mid=(t[id][root].l+t[id][root].r)/2;
    if(x<=mid)
        ret+=query(x,y,ls,id);
    if(y>mid)
        ret+=query(x,y,rs,id);
    return ret;
}
//-----------以上为线段树------------------ 
struct node
{
	int l,r,a,b,id;
}q[114514];
int n,m,a[114514];
int size,belong[114514];
int cnt[114514];
int ans[114514],ans1[114514];
int l=1,r;
void add(int x,int i)
{
	++cnt[a[x]];
	if(cnt[a[x]]==1)
		addt(a[x],1,1,2);
	addt(a[x],1,1,1);
}
void del(int x,int i)
{
	--cnt[a[x]];
	if(!cnt[a[x]])
		addt(a[x],1,-1,2);
	addt(a[x],1,-1,1);
}
bool cmp(node x,node y)
{
	if(belong[x.l]==belong[y.l])
		return x.r<y.r;
	return belong[x.l]<belong[y.l];
}
int main()
{
	cin>>n>>m;
	bld(1,114514,1,1);
	bld(1,114514,1,2);
	size=sqrt(n);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		belong[i]=i/size+1;
	for(int i=1;i<=m;i++)
		cin>>q[i].l>>q[i].r>>q[i].a>>q[i].b,q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l)
			del(l++,i);
		while(l>q[i].l)
			add(--l,i);
		while(r<q[i].r)
			add(++r,i);
		while(r>q[i].r)
			add(r--,i);
		ans[q[i].id]=query(q[i].a,q[i].b,1,1);
		ans1[q[i].id]=query(q[i].a,q[i].b,1,2);
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<" "<<ans1[i]<<endl;
}