#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 1e5 + 10;
int c[MAXN],siz,ex[MAXN],cnt[MAXN],id[MAXN],num[MAXN],maxx=0;
struct node{
	int l,r,a,b,id;
}e[MAXN];
struct data{
	int x,y;
}ans[MAXN];
bool cmp(node x,node y){
	if((x.l-1)/siz==(y.l-1)/siz) return x.r<y.r;
	return x.l/siz<y.l/siz;
}
void add(int x){
	cnt[x]++;
	ex[id[x]]++;
	if(cnt[x]<=1) num[id[x]]++;
}
void del(int x){
	cnt[x]--;
	ex[id[x]]--;
	if(!cnt[x]) num[id[x]]--;
}
int calc1(int x,int y){
	int ret=0 ; 
	y=min(y,maxx); 
	if(x>maxx) return 0; 
	int nx=id[x]+1; 
	int ny=id[y]-1;
	if(id[x]==id[y]){
		FL(i,x,y) ret+=cnt[i];
		return ret; 
	}
	FL(i,nx,ny) ret+=ex[i];
	int now=x;
	while(now<=maxx&&id[now]==id[x]) ret+=cnt[now],now++;
	now=y;
	while(now>=0&&id[now]==id[y]) ret+=cnt[now],now--;
	return ret;
}
int calc2(int x,int y){
	int ret=0; 
	y=min(y,maxx); 
	if(x>maxx) return 0 ; 
	int nx=id[x]+1; 
	int ny=id[y]-1;
	if(id[x]==id[y]){
		FL(i,x,y) ret+=(bool)cnt[i];
		return ret; 
	}
	FL(i,nx,ny) ret+=num[i];
	int now=x;
	while(now<=maxx&&id[now]==id[x]) ret+=(bool)cnt[now],now++;
	now=y;
	while(now>=0&&id[now]==id[y]) ret+=(bool)cnt[now],now--;
	return ret;
}
int main(){
	int n,m,l1=1,r1=0,l,r,a,b;
	scanf("%d%d",&n,&m);
	siz=sqrt(n);
	FL(i,1,n) scanf("%d",&c[i]),maxx=max(maxx,c[i]);
	FL(i,1,m) scanf("%d%d%d%d",&l,&r,&a,&b),e[i].id=i;
	sort(e+1,e+m+1,cmp);
	siz=sqrt(maxx);
	FL(i,1,maxx) id[i]=i/siz;
	FL(i,1,m){
		int le=e[i].l,ri=e[i].r,tmp=e[i].id;
		while(l1>le) l1--,add(c[l1]);
		while(r1<ri) r1++,add(c[r1]);
		while(l1<le) del(c[l1]),l1++;
		while(r1>ri) del(c[r1]),r1--;
		ans[tmp].x=calc1(a,b);
		ans[tmp].y=calc2(a,b);
	}
	FL(i,1,m) printf("%d %d\n",ans[i].x,ans[i].y);
	return 0;
}