test

#include<iostream>
#include<algorithm>
#include<tuple>
#include<map>
#include<cassert>
#ifdef ONLINE_JUDGE
#define getchar() (p_==q_&&(q_=(p_=b_)+fread(b_,1,s_,stdin),p_==q_)?-1:*p_++)
#define putchar(x_) ((r_-o_<s_)?(*r_++=x_):(flush(),r_=o_,*r_++=x_))
#endif
#define inline inline __attribute__((__always_inline__))
#define flush() (fwrite(o_,r_-o_,1,stdout),fflush(stdout),0)
using namespace std;constexpr int s_=1<<20;char b_[s_],o_[s_],*p_=b_,*q_=b_,*r_=o_;template<class T_>inline bool fr(T_&x_){x_=0;char c_=0,f_=0;do{if(c_=='-')f_=1;if((c_=getchar())==-1)return 0;}while(c_<48||c_>57);do {x_=x_*10+c_-48;if((c_=getchar())==-1)break;}while(c_>47&&c_<58);if(f_)x_=-x_;return 1;}template<class T_>inline void fw(T_ x_){char d_[40],l_=-1;if(x_<0)x_=-x_,putchar('-');do d_[++l_]=x_%10+48;while(x_/=10);do putchar(d_[l_]);while(~--l_);}

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

int n,m;
int a[maxn];
struct _qs{int l,r,A,B,id,blk;}qs[(int)1e6+10];
int ans[(int)1e6+10];

#define bsiz 200
#define _blk(x) ((x)-1)/bsiz+1
int cnt[maxn];int sum[bsiz+10];
inline void ins(int i){
    if(cnt[a[i]]==0)sum[_blk(a[i])]++;
    cnt[a[i]]++;
}
inline void del(int i){
    cnt[a[i]]--;
    if(cnt[a[i]]==0)sum[_blk(a[i])]--;
}
inline int query(int A,int B){
    int lid=_blk(A),rid=_blk(B);int res=0;
    if(lid==rid){
        for(int i=A;i<=B;i++)res+=!!cnt[i];
        return res;
    }
    for(int i=A;i<=lid*bsiz;i++)res+=!!cnt[i];
    for(int j=lid+1;j<=rid-1;j++)res+=sum[j];
    for(int i=B;i>=(rid-1)*bsiz+1;i--)res+=!!cnt[i];
    return res;
}
#undef bsiz
inline void modui(){
    int bsiz=__builtin_ceil(n/__builtin_pow(m,0.5));
    for(int i=1;i<=m;i++){
        int l,r,A,B;fr(l),fr(r),fr(A),fr(B);
        qs[i]={l,r,A,B,i,(l-1)/bsiz+1};
    }
    sort(qs+1,qs+m+1,[](const _qs &a,const _qs &b){
        if(a.blk!=b.blk)return a.blk<b.blk;
        return a.blk&1?a.r<b.r:a.r>b.r;
    });
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l>qs[i].l)ins(--l);
        while(r<qs[i].r)ins(++r);
        while(l<qs[i].l)del(l++);
        while(r>qs[i].r)del(r--);
        ans[qs[i].id]=query(qs[i].A,qs[i].B);
    }
}

signed main(){
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);

    fr(n),fr(m);
    for(int i=1;i<=n;i++)fr(a[i]);
    modui();
    for(int i=1;i<=m;i++)fw(ans[i]),putchar(10);
    exit(flush());
}