rt，QwQ

#include<bits/stdc++.h>
using namespace std;

inline char gc(){static char buf[1048576],*p1,*p2;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++;}
inline int read(){int w=1,c=0;char ch=gc();for(;ch>'9'||ch<'0';ch=gc()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=gc()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
inline void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}

const int N=1e5+5,B=350,MN=1e5;
int n,m,a[N],belong[N],ans1[N],ans2[N];
struct query{
	int id,l,r,a,b;
	bool operator <(query b){
		if(belong[l]==belong[b.l]) return r<b.r;
		else return belong[l]<belong[b.l];
	}
}q[N];
struct fk{
	int L[B],R[B],bel[N],d[N],s[B],bk=400,s2[B];
	void init(){
		for(int i=1;i<=MN;i++){bel[i]=ceil(1.0*i/bk);}
		for(int i=1;i<=bel[MN];i++){
			L[i]=R[i-1]+1;
			R[i]=i*bk;
		}
		R[bel[MN]]=MN;
	}
	void add(int x,int y){
		if(d[a[x]]==0) s[bel[a[x]]]++;
		d[a[x]]+=y;s2[bel[a[x]]]+=y;
		if(d[a[x]]==0) s[bel[a[x]]]--;
	}
	int ask(int l,int r){
		int ans=0;
		if(bel[l]==bel[r]){
			for(int i=l;i<=r;i++){if(d[i]) ans++;}
			return ans;
		}
		for(int i=l;i<=R[bel[l]];i++) if(d[i]) ans++;
		for(int i=L[bel[r]];i<=r;i++) if(d[i]) ans++;
		for(int i=bel[l]+1;i<=bel[r]-1;i++) ans+=s[i];
		return ans;
	}
	int ask2(int l,int r){
		int ans=0;
		if(bel[l]==bel[r]){
			for(int i=l;i<=r;i++) ans+=d[i];
			return ans;
		}
		for(int i=l;i<=R[bel[l]];i++) ans+=d[i];
		for(int i=L[bel[r]];i<=r;i++) ans+=d[i];
		for(int i=bel[l]+1;i<=bel[r]-1;i++) ans+=s2[i];
		return ans;
	}
}qwq;

signed main(){
	ios::sync_with_stdio(0);cin.tie(nullptr);
	n=read(),m=read();int bk=pow(n,0.5);
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) belong[i]=i/bk+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;
	}
	qwq.init();
	sort(q+1,q+n+1);
	for(int i=1,L=1,R=0;i<=m;i++){
		while(L>q[i].l) qwq.add(--L,1);
		while(R<q[i].r) qwq.add(++R,1);
		while(L<q[i].l) qwq.add(L++,-1);
		while(R>q[i].r) qwq.add(R--,-1);
		ans1[q[i].id]=qwq.ask2(q[i].a,q[i].b);
		ans2[q[i].id]=qwq.ask(q[i].a,q[i].b);
	}
	for(int i=1;i<=m;i++){
		print(ans1[i]);putchar(' ');print(ans2[i]);putchar('\n');
	}
	return 0;
}