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

#define ll long long
const int maxn = 1e5 + 10;

struct node{
	int idx, l, r, x, y, block;
}p[maxn];

int T, n, m, L, R, X, Y, tmp1, tmp2, cnt[maxn];
int a[maxn], ans1[maxn], ans2[maxn];

bool cmp(node x, node y){
	if(x.block == y.block){
		if(x.r == y.r){
			if(x.x == y.x) return x.y < y.y;
			return x.x < y.x;	
		}
		return x.r < y.r;
	}
	return x.l < y.l;
}

void upd1(int x){
	tmp1 += cnt[x];
	if(cnt[x]) tmp2++; 
}

void upd2(int x){
	tmp1 -= cnt[x];
	if(cnt[x]) tmp2--;
}

void add(int x){
	cnt[x]++;
	if(X <= x && x <= Y){
		tmp1++;
		if(cnt[x] == 1) tmp2++;	
	}
}

void del(int x){
	cnt[x]--;
	if(X <= x && x <= Y){
		tmp1--;
		if(!cnt[x]) tmp2--;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	T = n / sqrt(m) + 1;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++){
		cin >> p[i].l >> p[i].r >> p[i].x >> p[i].y;
		p[i].idx = i, p[i].block = (p[i].l - 1) / T + 1;
	}
	sort(p + 1, p + m + 1, cmp);
	L = 1, R = 0, X = 0, Y = 0;
	for(int i = 1; i <= m; i++){
		while(X > p[i].x) upd1(--X);
		while(Y < p[i].y) upd1(++Y);
		while(X < p[i].x) upd2(X++);
		while(Y > p[i].y) upd2(Y--);
		while(L > p[i].l) add(a[--L]);
		while(R < p[i].r) add(a[++R]);
		while(L < p[i].l) del(a[L++]);
		while(R > p[i].r) del(a[R--]);
		ans1[p[i].idx] = tmp1, ans2[p[i].idx] = tmp2;
	}
	for(int i = 1; i <= m; i++)
		cout << ans1[i] << " " << ans2[i] << endl;
	return 0;
}