看到除法相关容易想到根号分治。
先对 \(x,y\) 进行讨论，不妨令 \(0\le x,y<m\)。
\(x<y\) 时，当满足 \(a_i+y < m\) 或 \(a_i+x\ge m\) 时，即当 \(a_i<m-y\) 或 \(a_i\ge m-x\) 满足 \((a_i+x)\bmod m<(a_i+y)\bmod m\)，即 \(a_i \bmod m\in [0,m-y-1]\bigcup[m-x,m-1]\)。
\(x=y\) 时，无解。
\(x>y\) 时，满足 \(a_i+x\ge m\) 且 \(a_i+y<m\) 时成立，即 \(a_i\bmod m\in[0,m-y-1]\bigcap[m-x,m-1]\)。也可以交换 \(x,y\) 后按照方案一计算，然后用总方案数减去它即可。
这时候问题可以转化为每次求当前区间模 \(m\) 小于 \(x\) 的数的个数，先将区间容斥一下，\(w(l,r,u,d,m)=w(1,r,u,d,m)-w(1,l-1,u,d,m)\)。
设定阈值 \(B\)。
当 \(m\le B\) 时，由于 \(m\) 的取值只有 \(B\) 个。可将 \(w\) 看作一个询问，按 \(w\) 的第二维排序，变为插入一个数 ，查询小于 \(x\) 的数的个数，共有 \(\mathcal{O}(nB)\) 次插入，\(\mathcal{O}(q)\) 次查询,若直接使用树状数组维护，复杂度为 \(\mathcal{O}(m\log B+nB\log B)\)。但这样显然是不可以接受的。发现两边差异较大，可以使用分块来平衡。
当 \(m>B\) 时，先按 \(w\) 的第二维排序。每次插入一个数或查询一段区间的和。但是查询是通过枚举商，即会查询 \(\dfrac{qm}{B}\) 次。同理可以使用分块维护块内及块间的前缀和，即可做到修改 \(\mathcal{O}(\sqrt{n})\)，查询 \(\mathcal{O}(1)\) 了。
第一个块长取 \(20\)，第二个块长取 \(320\)，\(B\) 取 \(500\) 可过。
时间复杂度：\(\mathcal{O}(nB+n\sqrt{n}+\dfrac{qm}{B})\)。
代码：
const int N=1e5+10,M=5e5+10,B=520;
int n,Q,cnt,c;
int val[N],f[N],si[N],so[N],bel[N];
int a[N],ans[M];
struct que{
int x,u,d,m,typ,id;
} qt[M<<2],unt;
vector<que> qa,qb;
bool cmp1(que a,que b){ return a.m!=b.m?a.m<b.m:a.x<b.x; }
bool cmp2(que a,que b){ return a.x<b.x; }
void ins(int p,int x){
val[p]++;
for(int i=p;i<=bel[p]*c-1;i++)
si[i]++;
for(int i=bel[p];i<=bel[N-1];i++)
so[i]++;
}
int query(int l,int r){
int x=bel[l],y=bel[r];
if(x==y)
return si[r]-(l%c>0?si[l-1]:0);
return (si[x*c-1]-(l%c>0?si[l-1]:0))+si[r]+(so[y-1]-so[x]);
}
int main(){
unt=(que){0,0,0,0,0,0};
n=read(),Q=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1,l,r,x,y,m;i<=Q;i++){
l=read(),r=read(),x=read(),y=read(),m=read(); x%=m,y%=m;
if(x==y) continue;
int ty;
if(x>y) ty=-1,swap(x,y),ans[i]=r-l+1;
else ty=1;
if(l>1){
qt[++cnt]=(que){l-1,m-y-1,0,m,ty*-1,i};
qt[++cnt]=(que){l-1,m-1,m-x,m,ty*-1,i};
}
qt[++cnt]=(que){r,m-y-1,0,m,ty,i};
qt[++cnt]=(que){r,m-1,m-x,m,ty,i};
}
qa.pb(unt),qb.pb(unt);
for(int i=1;i<=cnt;i++){
if(qt[i].m<=B)
qa.pb(qt[i]);
else
qb.pb(qt[i]);
}
sort(qa.begin(),qa.end(),cmp1);
c=18;
for(int i=0;i<=B;i++)
bel[i]=i/c+1;
for(int i=1,now=0;i<(int)qa.size();i++){
if(qa[i].m!=qa[i-1].m){
for(int j=0;j<=B;j++) val[j]=0;
for(int j=0;j<=30;j++) f[j]=0;
now=0;
}
for(int j=now+1;j<=qa[i].x;j++){
val[a[j]%qa[i].m]++;
f[bel[a[j]%qa[i].m]]++;
}
now=qa[i].x;
int res=0;
for(int j=1;j<bel[qa[i].u];j++) res+=f[j],assert(f[j]<=n);
for(int j=(bel[qa[i].u]-1)*c;j<=qa[i].u;j++) res+=val[j],assert(val[j]<=n);
if(qa[i].d>0){
for(int j=1;j<bel[qa[i].d-1];j++) res-=f[j];
for(int j=(bel[qa[i].d-1]-1)*c;j<qa[i].d;j++) res-=val[j];
}
ans[qa[i].id]+=res*qa[i].typ;
}
sort(qb.begin(),qb.end(),cmp2);
c=sqrt(N-1);
for(int i=0;i<N;i++)
bel[i]=i/c+1;
for(int i=1,now=0;i<(int)qb.size();i++){
for(int j=now+1;j<=qb[i].x;j++)
ins(a[j],1);
now=qb[i].x;
int l=qb[i].d,r=qb[i].u,res=0;
for(int j=0;;j++){
if(l+j*qb[i].m>N-1)
break;
res+=query(l+j*qb[i].m,min(r+j*qb[i].m,N-1));
}
ans[qb[i].id]+=res*qb[i].typ;
}
for(int i=1;i<=Q;i++) write(ans[i]),putchar('\n');
return 0;
}