不知道该给这题贴什么标签了，但是这是一道好题
1.注意这道题的询问是满足区间减法的，我们可以把一个询问拆成两个询问离线搞搞，这个思想在后面会见到
2.分类的思想，这道题的求相同余数看似很烦，实际上我们发现每个数只有10^4，不难发现
当p>=100时，我们可以完全不虚的穷举k,k+p*1,k+p*2……，计算每个数出现的次数
当p<100时,我们完全可以直接记录f[p,k]代表到现在出现的次数
因此这题做法就很明显了
type node=record
x,w,p,k:longint;
end; var q:array[..] of node;
a,f2:array[..] of longint;
f1:array[..,..] of longint;
ans:array[..,..] of longint;
mx,j,l,r,p,k,n,m,i,t:longint; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=q[(l+r) shr ].x;
repeat
while q[i].x<x do inc(i);
while x<q[j].x do dec(j);
if not(i>j) then
begin
swap(q[i],q[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; begin
readln(n,m);
for i:= to n do
begin
read(a[i]);
if mx<a[i] then mx:=a[i];
end;
for i:= to m do
begin
readln(l,r,p,k);
inc(t); q[t].p:=p; q[t].k:=k; q[t].x:=r; q[t].w:=i*;
inc(t); q[t].p:=p; q[t].k:=k; q[t].x:=l-; q[t].w:=i*-;
end;
sort(,*m);
t:=;
while q[t].x= do inc(t);
for i:= to n do
begin
inc(f2[a[i]]);
for j:= to do
inc(f1[j,a[i] mod j]); while q[t].x=i do
begin
if q[t].p> then
begin
for j:= to mx div q[t].p do
inc(ans[q[t].w shr +q[t].w mod ,q[t].w mod ],f2[q[t].p*j+q[t].k]);
end
else ans[q[t].w shr +q[t].w mod ,q[t].w mod ]:=f1[q[t].p,q[t].k];
inc(t);
end;
end;
for i:= to m do
writeln(ans[i,]-ans[i,]);
end.