rt

#include<bits/stdc++.h>
#define afor(x,y,z) for(int x=y;x<=z;x++)
#define bfor(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
typedef const int cint;
cint N=110000,M=350;
int n,m,b[N],bl[N],ans1[N],ans2[N],cnt[N];
int blcnt1[M],blcnt2[M],L[M],R[M];
struct rec{
	int l,r,a,b,id,bl;
} a[N];
bool cmp(rec a,rec b) {
	if(a.bl==b.bl) return a.r<b.r;
	return a.l<b.l;
}
void fix(int x,int y) {
	cnt[x]+=y;
	blcnt1[bl[x]]+=y;
	if(cnt[x]==1) blcnt2[bl[x]]++;
	if(!cnt[x]) blcnt2[bl[x]]--;
}
int query1(int l,int r) {
	int ret=0;
	if(bl[l]==bl[r]) afor(i,l,r) ret+=cnt[i];
	else {
		afor(i,l,R[bl[l]]) ret+=cnt[i];
		afor(i,bl[l]+1,bl[r]-1) ret+=blcnt1[i];
		afor(i,L[bl[r]],r) ret+=cnt[i];
	}
	return ret;
}
int query2(int l,int r) {
	int ret=0;
	if(bl[l]==bl[r]) afor(i,l,r) ret+=(bool)cnt[i];
	else {
		afor(i,l,R[bl[l]]) ret+=(bool)cnt[i];
		afor(i,bl[l]+1,bl[r]-1) ret+=blcnt2[i];
		afor(i,L[bl[r]],r) ret+=(bool)cnt[i];
	}
	return ret;
}
int main() {
	scanf("%d%d",&n,&m);
	int block=sqrt(n),k=320;
	afor(i,1,n) scanf("%d",&b[i]);
	afor(i,1,m) {
		scanf("%d%d",&a[i].l,&a[i].r);
		scanf("%d%d",&a[i].a,&a[i].b);
		a[i].id=i,a[i].bl=a[i].l/block;
	}
	afor(i,1,1e5) bl[i]=(i-1)/k+1;
	afor(i,1,k) L[i]=R[i-1],R[i]=i*k;
	sort(a+1,a+m+1,cmp);
	int l=1,r=0;
	afor(i,1,m) {
		while(r<a[i].r) fix(b[++r],1);
		while(r>a[i].r) fix(b[r--],-1);
		while(l<a[i].l) fix(b[l++],-1);
		while(l>a[i].l) fix(b[--l],1);
		ans1[a[i].id]=query1(a[i].a,a[i].b);
		ans2[a[i].id]=query2(a[i].a,a[i].b);
	}
	afor(i,1,m) printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}