#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
#define rc(x) min(N-5,x*sizz)
#define lc(x) (x*sizz-sizz+1)
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=1e5+5;
int n,m,siz,sizz,a[N],k[N],kz[N],t[N],cnt[N],cnt2[N],output1[N],output2[N];
struct node{
	int L,R,A,B,I;
}q1[N];
inline bool comp(node &o,node &p){
	if (k[o.L]==k[p.L]&&k[o.L]&1==0) return o.R<p.R;
	if (k[o.L]==k[p.L]) return o.R>p.R;
	return k[o.L]<k[p.L];
}
inline void add1(int x){
	cnt[kz[a[x]]]++;
	if (t[a[x]]++==0) cnt2[kz[a[x]]]++;
}
inline void del1(int x){
	cnt[kz[a[x]]]--;
	if (--t[a[x]]==0) cnt2[kz[a[x]]]--;
}
inline int query1(int l,int r){
	int ans=0;
	if (kz[l]==kz[r]){
		for (int i=l;i<=r;i++) ans+=t[i];
		return ans;
	}
	for (int i=l;i<=rc(l);i++) ans+=t[i];
	for (int i=r;i>=lc(r);i--) ans+=t[i];
	for (int i=kz[l]+1;i<=kz[r]-1;i++) ans+=cnt[i];
	return ans;
}
inline int query2(int l,int r){
	int ans=0;
	if (kz[l]==kz[r]){
		for (int i=l;i<=r;i++) ans+=(t[i]!=0);
		return ans;
	}
	for (int i=l;i<=rc(l);i++) ans+=(t[i]!=0);
	for (int i=r;i>=lc(r);i--) ans+=(t[i]!=0);
	for (int i=kz[l]+1;i<=kz[r]-1;i++) ans+=cnt2[i];
	return ans;
}
void case1(){
	int l=1,r=0;
	for (int i=1;i<=m;i++){
		int L=q1[i].L,R=q1[i].R;
		while (l<L) del1(l++);
		while (l>L) add1(--l);
		while (r<R) add1(++r);
		while (r>R) del1(r--);
		output1[q1[i].I]=query1(q1[i].A,q1[i].B);
		output2[q1[i].I]=query2(q1[i].A,q1[i].B);
	}
}
signed main(){
//	freopen("P4396_1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),m=read();
	siz=sqrt(n),sizz=sqrt(N-5);
	for (int i=1;i<=n;i++){
		k[i]=(i-1)/siz+1;
		a[i]=read();
	}
	for (int i=1;i<=N-5;i++){
		kz[i]=(i-1)/sizz+1;
	}
	for (int i=1;i<=m;i++){
		q1[i].L=read();
		q1[i].R=read();
		q1[i].A=read();
		q1[i].B=read();
		q1[i].I=i;
	}
	sort(q1+1,q1+m+1,comp);
	case1();
	for (int i=1;i<=m;i++){
		cout<<output1[i]<<' '<<output2[i]<<'\n';
	}
	return 0;
}
/*
5 1
1 5 4 2 2
1 3 1 5
*/