Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
inline ll read(){
	ll x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
#define int long long
int ans[5000005],ans1[5000005],nans;
int a[5000005];
map<int,int>num;
int n=read(),m=read(),T=sqrt(n);
struct node{
	int l,r,a,b,id;
}q[5000005];
bool operator<(node a,node b){
	if(a.l/T==b.l/T) return (a.r<b.r)^((a.l/T)&1);
	else return a.l<b.l;
}
int bll=sqrt(1000000);
struct blksz{
	int L[40000],R[40000],bl[50000005],a[50000005],sum[40000],cnt[40000];
    void init(int x){
		for(int i=1;i<=(x+bll-1)/bll;i++){
			L[i]=i*bll-bll+1;
			R[i]=min(i*bll,x);
			sum[i]=0;
			for(int j=L[i];j<=R[i];j++) bl[j]=i,a[j]=0;
		}
	}
	void add(int x){
		if(x<0) return; 
		a[x]++;
		sum[bl[x]]++;
		if(a[x]==1)cnt[bl[x]]++;
	}
	void del(int x){
		if(x<0) return; 
		a[x]--;
		sum[bl[x]]--;
		if(a[x]==0)cnt[bl[x]]--;
	}
	int querysum(int l,int r){
		int ans=0;
		if(bl[l]==bl[r]) for(int i=l;i<=r;i++) ans+=a[i];
		else{
			for(int i=l;i<=R[bl[l]];i++) ans+=a[i];
			for(int i=bl[l]+1;i<bl[r];i++) ans+=sum[i];
			for(int i=L[bl[r]];i<=r;i++) ans+=a[i]; 
		}
		return ans;
	}
	int querycnt(int l,int r){
		int ans=0;
		if(bl[l]==bl[r]) for(int i=l;i<=r;i++) ans+=a[i]>0;
		else{
			for(int i=l;i<=R[bl[l]];i++) ans+=a[i]>0;
			for(int i=bl[l]+1;i<bl[r];i++) ans+=cnt[i];
			for(int i=L[bl[r]];i<=r;i++) ans+=a[i]>0; 
		}
		return ans;
	}
	void print(int l,int r){
		printf("___");
		for(int i=l;i<=r;i++){
			printf("%d:%d ",i,a[i]);
		}
		putchar(10);
	}
	void printl(int l,int r){
		printf("_ _ _");
		for(int i=l;i<=r;i++){
			printf("%d:%d,%d ",i,sum[i],cnt[i]);
		}
		putchar(10);
	}
}t;
void add(int x){
	t.add(a[x]);
}
void del(int x){
	t.del(a[x]);
}
signed main(){
	t.init(1000000);
	for(int i=1;i<=n;i++) a[i]=read();
	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;
	}
	sort(q+1,q+m+1);
	int nl=1,nr=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(nl>ql){
			add(--nl);
		}
		while(nr<qr){
			add(++nr);
		}
		while(nl<ql){
			del(nl++);
		}
		while(nr>qr){
			del(nr--);
		}
		ans[q[i].id]=t.querysum(q[i].a,q[i].b);
		ans1[q[i].id]=t.querycnt(q[i].a,q[i].b);
//		t.print(q[i].a,q[i].b);
//		t.printl(t.bl[q[i].a],t.bl[q[i].b]);
	}
	for(int i=1;i<=m;i++) printf("%lld %lld\n",ans[i],ans1[i]);
}

record