#include<bits/stdc++.h>
using namespace std;
struct query{
	int l,r,m,x,y,ans,org,R,L;
}q[500005];
int n,li[100005],mp[100005],m,B,tmpl,tmpr,c,tmpl2,tmpr2;
int bucket[505][505];
int block[505][505];
int cnt[100005];
int qzh[505];
int pos[100005],posl[100005],posr[100005];

void adde(int x){
//	cout<<"Adde "<<li[x]<<endl;
	cnt[li[x]]++;
	
	int blockid=pos[li[x]];
	for(int i=li[x];i<=posr[blockid];i++){
		block[blockid][i-posl[blockid]+1]++;
	}
	for(int i=blockid;i<=c;i++)qzh[i]++;
}
void del(int x){
//	cout<<"Del "<<li[x]<<endl;
	cnt[li[x]]--;
	int blockid=pos[li[x]];
	for(int i=li[x];i<=posr[blockid];i++)block[blockid][i-posl[blockid]+1]--;
	for(int i=blockid;i<=c;i++)qzh[i]--;
}void work1(int i){
	
	while(tmpl2<q[i].l){
		bucket[q[i].m][li[tmpl2]]--;
		
		tmpl2++;
	}
	while(tmpr2>q[i].r){
		bucket[q[i].m][li[tmpr2]]--;
		tmpr--;
	}
	while(tmpl2>q[i].l){
		tmpl2--;
		bucket[q[i].m][li[tmpl2]]++;
	}
	while(tmpr2<q[i].r){
		tmpr2++;
		bucket[q[i].m][li[tmpr2]]++;
	}
	q[i].ans=bucket[q[i].m][q[i].R]-bucket[q[i].m][q[i].L-1];
	if(q[i].x<q[i].y)q[i].ans=(q[i].R-q[i].L+1)-q[i].ans;
}
int ask(int mark){
	return qzh[pos[mark]-1]+block[pos[mark]][mark-posl[pos[mark]]+1];
}
bool cmp2(query a,query b){
	return a.org<b.org;
}
void work2(int i){
	for(int i=1;i<=c;i++){
	}
	if(q[i].R<q[i].L)return;
//	cout<<tmpl<<" "<<tmpr<<endl;
	while(tmpl<q[i].l)del(tmpl++);
	while(tmpr>q[i].r)del(tmpr--);
	while(tmpl>q[i].l)adde(--tmpl);
	while(tmpr<q[i].r)adde(++tmpr);
	int R=q[i].R,L=q[i].L;
	while(L<=n&&R<=n){
		q[i].ans+=ask(R)-ask(L-1);
		R+=q[i].m;
		L+=q[i].m;
	}
	if(q[i].x<q[i].y)q[i].ans=(q[i].r-q[i].l+1)-q[i].ans;
}
bool cmp(query a,query b){
	int al=a.l/B,bl=b.l/B;
	if(al!=bl)return al<bl;
	if(al%2==0)return a.r>b.r;
	else return a.r<b.r;
}
int main(){
	cin>>n>>m;
	
	B=sqrt(n);
	c=0;
	pos[0]=-1;
	for(int i=1;i<=n;i++){
		int tmpa=i/B;
		if(tmpa!=(i-1)/B||i==1){
			c++;posl[c]=i;
		}
		if(tmpa!=(i+1)/B||i==n){
			posr[c]=i;
		}
		pos[i]=c;
	}
//	for(int i=1;i<=c;i++)cout<<posl[i]<<" "<<posr[i]<<endl;
//	cout<<(7%6);
	for(int i=1;i<=n;i++)cin>>li[i];
	//tmpl=tmpr=1;
//	adde(1);
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r>>q[i].x>>q[i].y>>q[i].m;
		q[i].x%=q[i].m;
		q[i].y%=q[i].m;
		q[i].L=q[i].m-max(q[i].x,q[i].y);
		q[i].R=q[i].m-min(q[i].x,q[i].y)-1;
		q[i].org=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=m;i++){
		cout<<q[i].l<<" "<<q[i].r<<endl;
		if(q[i].m<=B){
			work1(i);
			
		}
		else{
			work2(i);
		}
	}	
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++)cout<<q[i].ans<<endl;
}