#include<bits/stdc++.h>
using namespace std;
const int nn=1e5+5;
int n,m,a[nn],block,ans1[nn],ans2[nn],b[nn];
//ans1 总数量
//ans2 数值数量 
struct node
{
	int l,r,a,b,id,tot1,tot2;
};
node x[nn];
bool cmp(node l1,node l2)
{
	if((l1.l-1)/block+1==(l2.l-1)/block+1) return l1.r<l2.r;
	return l1.l<l2.l;
}
void add(int l)
{
	if(b[a[l]]==0){
		ans1[(a[l]-1)/block+1]++;
		ans2[(a[l]-1)/block+1]++;
	}
	else ans1[(a[l]-1)/block+1]++;
	b[a[l]]++;
//	cout<<l<<" "<<(a[l]-1)/block+1<<" "<<b[a[l]]<<" "<<ans1[(a[l]-1)/block+1]<<endl;
}
void dec(int l)
{
	
	//cout<<l<<" !"<<(a[l]-1)/block+1<<endl;
	if(b[a[l]]==1){
		ans1[(a[l]-1)/block+1]--;
		ans2[(a[l]-1)/block+1]--;
	}
	else ans1[(a[l]-1)/block+1]--;
	b[a[l]]--;
}
int query1(int a,int bb)
{
	int ans=0;
	for(int i=a;i<=bb;i++) ans+=b[i];
	return ans;
}
int query2(int a,int bb)
{
	int ans=0;
	for(int i=a;i<=bb;i++){
		if(b[i]>0) ans++;
	}
	return ans;
}
bool cmp2(node l1,node l2)
{
	return l1.id<l2.id;
}
int main()
{
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
//	std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
	cin>>n>>m;
	block=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) 
	cin>>x[i].l>>x[i].r>>x[i].a>>x[i].b,x[i].id=i;
	sort(x+1,x+m+1,cmp);
	block=sqrt(nn-5);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>x[i].l){ 
			l--;
			add(l);
		}
		while(l<x[i].l){
			dec(l);
			l++;
		}
		while(r<x[i].r){
			r++;
			add(r);
		}
		while(r>x[i].r){
			dec(r);
			r--;
		}
	//	for(int i=1;i<=nn-5;i++) cout<<b[i]<<" ";
	//	cout<<endl;
	//	for(int j=1;j<=sqrt(nn-5);j++) cout<<ans1[j]<<" "<<ans2[j]<<endl;
	//	cout<<endl;
		int l0=(x[i].a-1)/block+1,r0=(x[i].b-1)/block+1;
	//	cout<<l0<<" !"<<r0<<endl;
		int sum1,sum2;
		if(l0==r0){
			sum1=query1(x[i].a,x[i].b);
			sum2=query2(x[i].a,x[i].b);
		}
		else{
			sum1=query1(l,l0*block)+query1((r0-1)*block+1,r);
			sum2=query2(l,l0*block)+query2((r0-1)*block+1,r);
	//		cout<<sum1<<" "<<sum2<<endl;
			for(int j=l0+1;j<=r0-1;j++){
				sum1+=ans1[j];
				sum2+=ans2[j];
			}
		//	cout<<sum1<<" "<<sum2<<endl;
		}
		x[i].tot1=sum1,x[i].tot2=sum2;
	}
	sort(x+1,x+m+1,cmp2);
	for(int i=1;i<=m;i++) cout<<x[i].tot1<<" "<<x[i].tot2<<endl;
	return 0;
}

70pts