RT 调了亿年了（

似乎是出现负值了 但并没看出来/kk

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define dec(x) fixed<<setprecision(x)
#define pii pair<int,int>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

template<class T> inline void rd(T &x){
	int fl=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	x*=fl;
}
template<class T> inline void wr(T x){
	if(x<0) x=-x,putchar('-');
	if(x<10){putchar(x+'0');return ;}
	int tmp[40]={0},cnt=0;
	while(x) tmp[cnt++]=x%10,x/=10;
	for(re i=cnt-1;i>=0;--i) putchar(tmp[i]+'0');
}

// ---------- IO ---------- //

const int N=1e5+5;
int n,m,len,a[N],ans[N][2];
struct question{
	int id,l,r,a,b,pos;
	inline bool operator <(const question &o){
		if(pos^o.pos) return pos<o.pos;
		return (pos&1)^(r<o.r);
	} 
}q[N];

struct Sqrt_On_Range{
	inline int block(int x){return (x-1)/len+1;}
	inline int L(int x){return (x-1)*len+1;}
	inline int R(int x){return x*len;}
	int cnt[N],s1[N],s2[N];
	inline void add(int x){if((++cnt[x])==1) ++s1[block(x)];++s2[block(x)];}
	inline void del(int x){if((--cnt[x])==0) --s1[block(x)];--s2[block(x)];}
	inline pii query(int x){
		int sum1=0,sum2=0,ed=block(x);
		for(re i=1;i<ed;++i) sum1+=s1[i],sum2+=s2[i];
		for(re i=L(ed);i<=x;++i) sum1+=(bool)cnt[i],sum2+=cnt[i];
		return mp(sum1,sum2);
	}
}S;

// ----------  ---------- //

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	rd(n);rd(m);len=305;
	for(re i=1;i<=n;++i) rd(a[i]);
	for(re i=1;i<=m;++i) rd(q[i].l),rd(q[i].r),rd(q[i].a),rd(q[i].b),q[i].id=i,q[i].pos=(q[i].l-1)/len+1;
	sort(q+1,q+m+1);
	int l=q[1].l,r=q[1].l-1;
	for(re i=1;i<=m;++i){
		while(l>q[i].l) S.add(a[--l]);
		while(r<q[i].r) S.add(a[++r]);
		while(l<q[i].l) S.del(a[l++]);
		while(r>q[i].r) S.del(a[r--]);
		pii a1=S.query(q[i].b),a2=S.query(q[i].a-1);
		ans[q[i].id][0]=a1.first-a2.first,ans[q[i].id][1]=a1.second-a2.second;
	}
	for(re i=1;i<=m;++i) wr(ans[i][1]),putchar(' '),wr(ans[i][0]),puts("");
	return 0;
}

// ---------- Main ---------- //