给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Ai mod p = k的值i的个数。

 

         第一行两个正整数n和m。

         第二行n个数，表示A1,A2,…,An。

         以下m行，每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。

 

         对于每个询问，输出一行，表示可行值i的个数。

 

 

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<cassert>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

	if(head==tail) {

		int l=fread(buffer,1,BufferSize,stdin);

		tail=(head=buffer)+l;

	}

	return *head++;

}

inline int read() {

    int x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

#define S 1200000

char pf[S],*o1=pf,*o2=pf+S;

#define ot(x) (o1==o2?fwrite(pf,1,S,stdout),*(o1=pf)++=x:*o1++=x)

inline void print(int x){static char s[10],*b;b=s;if(!x)*b++=48;for(;x;*b++=x%10+48,x/=10);for(;b--!=s;ot(*b));}

const int maxn=100010;

const int maxm=10010;

const int SIZE=50;

int n,m,A[maxn],ans[maxn];

struct Query {

	int x,p,k,id;

	bool operator < (const Query& ths) const {return x<ths.x;}

}Q[maxn<<1];

int cnt[maxm],B[55][55];

void Add(int v) {

	cnt[v]++;

	rep(i,1,SIZE) B[i][v%i]++;

}

int calc(int p,int k) {

	int ans=0;

	while(k<=10000) {

		ans+=cnt[k];

		k+=p;

	}

	return ans;

}

int main() {

	n=read();m=read();

	rep(i,1,n) A[i]=read();

	rep(i,1,m) {

		int l=read(),r=read(),p=read(),k=read();

		Q[i]=(Query){l-1,p,k,-i};Q[i+m]=(Query){r,p,k,i};

	}

	sort(Q+1,Q+2*m+1);int cur=0;

	rep(i,1,2*m) {

		while(cur<Q[i].x) Add(A[++cur]);

		int res=Q[i].p<=SIZE?B[Q[i].p][Q[i].k]:calc(Q[i].p,Q[i].k);if(Q[i].id<0) res=-res,Q[i].id=-Q[i].id;

		ans[Q[i].id]+=res;

	}

	rep(i,1,m) print(ans[i]),ot('\n');

	fwrite(pf,1,o1-pf,stdout);

	return 0;

}