#include<bits/stdc++.h>
using namespace std;
#define reg register
const int N = 100001;
#define lowbit(x) ((x) & -(x))
#define IOSIZE 1000000
extern "C"{
namespace io{
	static char in[IOSIZE],*p=in,*pp=in,out[IOSIZE],*q=out,ch[20],*t=ch;
	inline char gc(){return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?EOF:*p++;}
	inline int read(){
		reg int x=0;reg char ch,f=0;
		while(!isdigit(ch=gc()))f|=ch=='-';
		while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();
		return f?-x:x;
	}
	inline void write(int x,char sp){
		!x&&(*q++=48),x<0&&(*q++='-',x=-x);
		while(x)*t++=x%10+48,x/=10;
		while(t!=ch)*q++=*--t;
		*q++=sp;
	}
	inline void flush(){fwrite(out,1,q-out,stdout);}
}}
#define read io::read
#define write io::write
int tr1[N], tr2[N];
inline void add(int x, int v, int *tr) {
	for (; x <= N; x += lowbit(x)) tr[x] += v;
}
inline int query(int x, int *tr) {
	reg int sm = 0; 
	for (; x; x -= lowbit(x)) sm += tr[x]; 
	return sm;
}
int n, m, bl[N], a[N], cnt[N], res1[N], res2[N];
struct Node{
    int l, r, a, b, i;
}qry[N];
inline bool cmp(const Node&a, const Node&b) {
    return bl[a.l] != bl[b.r] ? bl[a.l] < bl[b.l] : bl[a.l] & 1 ? a.r > b.r : a.r < b.r;
}
inline void ins(int x) {
	add(a[x], 1, tr1);
	(++cnt[a[x]] == 1) && (add(a[x], 1, tr2), 0);
}
inline void del(int x) {
	add(a[x], -1, tr1); 
	(--cnt[a[x]] == 0) && (add(a[x], -1, tr2), 0);}
int main() {
    n = read(), m = read();
    int bsiz = pow(n*2, 1.0 / 3);
    for (reg int i = 1; i <= n; ++i) bl[i] = (i - 1) / bsiz + 1;
    for (reg int i = 1; i <= n; ++i) a[i] = read();
    for (reg int i = 1; i <= m; ++i)
        qry[i].l = read(), qry[i].r = read(), qry[i].a = read(), qry[i].b = read(), qry[i].i = i;
    sort(qry + 1, qry + m + 1, cmp);
    reg int l = 1, r = 0;
    for (reg int i = 1; i <= m; ++i) {
        for (; r < qry[i].r; ins(++r));
        for (; l > qry[i].l; ins(--l));
        for (; r > qry[i].r; del(r--));
        for (; l < qry[i].l; del(l++));
        res1[qry[i].i] = query(qry[i].b, tr1) - query(qry[i].a - 1, tr1);
        res2[qry[i].i] = query(qry[i].b, tr2) - query(qry[i].a - 1, tr2);
    }
    for (reg int i = 1; i <= m; ++i)
        write(res1[i],' '),  write(res2[i],'\n');
    io :: flush();
    return 0;
}