#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int w=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) w=w*10+ch-'0',ch=getchar();
	return w;
}
int que[500005];
int ql=1,qr;
int tr[500005][2],tot=0;
int f[500005][35][2],g[500005][35][2];
int id[500005];
int sum[500005],fail[500005];
char ch[500005];
vector<int> to[500005];
int insert(){
	int n=strlen(ch+1);
	int nw=0;
	for(int i=1;i<=n;i++){
		int way=ch[i]-'0';
		if(!tr[nw][way]) tr[nw][way]=++tot;
		nw=tr[nw][way];
	}
	return nw;
}
void build(){
	if(tr[0][0]) que[++qr]=tr[0][0];
	if(tr[0][1]) que[++qr]=tr[0][1];
	while(ql<=qr){
		int u=que[ql++];
		for(int k=0;k<2;k++){
			if(tr[u][k]){
				fail[tr[u][k]]=tr[fail[u]][k];
				que[++qr]=tr[u][k];
			}else tr[u][k]=tr[fail[u]][k];
		}
	}
	for(int i=0;i<=tot;i++) f[i][0][0]=tr[i][0],f[i][0][1]=tr[i][1];
	for(int k=1;k<30;k++){
		for(int i=0;i<=tot;i++){
			f[i][k][0]=f[f[i][k-1][0]][k-1][1];
			f[i][k][1]=f[f[i][k-1][1]][k-1][0];
		}
	}
	for(int i=2;i<=tot;i++) to[fail[i]].push_back(i);
}
int n,q;
int sl[100005],sr[100005];
int nw=0;
void solve(int nl,int nr){
	nr++;
	for(int i=0;i<30;i++){
		if((nl&(1<<i))&&nl+(1<<i)<=nr){
			int p=__builtin_popcount(nl);
			g[nw][i][p&1]++;
			// printf("%d %d %d\n",p&1,nw,i);
			nw=f[nw][i][p&1];
			nl+=(1<<i);
		}
	}
	for(int i=29;i>=0;i--){
		if((nr&(1<<i))&&!(nl&(1<<i))){
			int p=__builtin_popcount(nl);
			// printf("%d %d %d\n",p&1,nw,i);
			g[nw][i][p&1]++;
			nw=f[nw][i][p&1];
			nl+=(1<<i);
		}
	}
}
void pushtag(){
	for(int k=29;k;k--){
		for(int i=0;i<=tot;i++){
			g[i][k-1][0]+=g[i][k][0];
			g[f[i][k-1][0]][k-1][1]+=g[i][k][0];
			g[i][k-1][1]+=g[i][k][1];
			g[f[i][k-1][1]][k-1][0]+=g[i][k][1];
		}
	}
	for(int i=0;i<=tot;i++){
		for(int k=0;k<2;k++){
			sum[tr[i][k]]+=g[i][0][k];
		}
	}
}
void bfs(){
	for(int i=qr;i;i--){
		int u=que[i];
		sum[fail[u]]+=sum[u];
	}
}
main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&sl[i],&sr[i]);
	for(int i=1;i<=q;i++){
		scanf("%s",ch+1);
		id[i]=insert();
	}
	build();
	for(int i=1;i<=n;i++) solve(sl[i],sr[i]);
	pushtag();
	// for(int i=0;i<=tot;i++){
	// 	printf("%d %d %d %d",i,tr[i][0],tr[i][1],fail[i]);
	// 	printf("\n%d\n",sum[i]);       
	// }
	bfs();
	// for(int i=0;i<=tot;i++){
	// 	printf("%d %d %d %d",i,tr[i][0],tr[i][1],fail[i]);
	// 	printf("\n%d\n",sum[i]);       
	// }
	for(int i=1;i<=q;i++) printf("%lld\n",sum[id[i]]);
}
/*
3 7
2 6
1 3
4 8
0
00
1
11
101
0011010
1010011010011

1 1
2 3
10

1010011010011
*/