#include <bits/stdc++.h>
#define in(x) freopen(#x".in","r",stdin)
#define out(x) freopen(#x".out","w",stdout)
#define make(x) freopen(#x".in","w",stdout)
#define ll long long
#define int long long
#ifdef MY_COMPUTER
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define vector basic_string
#define pii array<int,2>

using namespace std;

inline int read()
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
template<typename _it>
void read(_it a,_it b){
	while(a!=b) (*a)=read(),a++;
}
template<typename _it>
void write(const char* form,_it a,_it b,int op=0){
	while(a!=b) printf(form,*a),a++;
	if(op) puts("");
}
int n,t,l[500010],r[500010];
char s[500010];
int tr[500010][2],fail[500010],siz[500010],cnt,ed[500010];
queue<int>q;
int f[500010][31][2],g[500010][31][2];
const int M=1ll<<31;
vector<int>e[500010];
void dfs(int u){for(int v:e[u]) dfs(v),siz[u]+=siz[v];}
signed main()
{
	//ios::sync_with_stdio(false);
	n=read(),t=read();
	for(int i=1;i<=n;i++) l[i]=read(),r[i]=read();
	for(int i=0,xl;i<t;i++){
		scanf("%s",s),xl=strlen(s);
		int x=0;
		for(int j=0,p;j<xl;j++){
			p=s[j]-'0';
			if(!tr[x][p]) tr[x][p]=++cnt;
			x=tr[x][p];
		}
		ed[i]=x;
	}
	if(tr[0][0]) q.push(tr[0][0]);
	if(tr[0][1]) q.push(tr[0][1]);
	while(!q.empty()){
		int u=q.front();q.pop();
		e[fail[u]]+=u;
		for(int x:{0,1})
			if(tr[u][x]) fail[tr[u][x]]=tr[fail[u]][x],q.push(tr[u][x]);
			else tr[u][x]=tr[fail[u]][x];
	}
	for(int i=0;i<=cnt;i++)
		f[i][0][0]=tr[i][0],f[i][0][1]=tr[i][1];
	for(int i=1;i<=30;i++)
		for(int u=0;u<=cnt;u++)
			f[u][i][0]=f[f[u][i-1][0]][i-1][1],
			f[u][i][1]=f[f[u][i-1][1]][i-1][0];
	for(int i=1,L,R,x,s=0;i<=n;i++){
		vector<pii>sp1,sp2;
		sp1.clear(),sp2.clear();
		L=l[i],R=r[i];
		for(L+=M-1,R+=M+1,x=0;L^R^1ll;L>>=1,R>>=1,x++){
			if(~L&1) sp1+={{x,__builtin_popcountll(l[i])&1}},l[i]+=1ll<<x;
			if(R&1) sp2+={{x,__builtin_popcountll(r[i]-(1<<x)+1)&1}},r[i]-=1ll<<x;
		}
		reverse(sp2.begin(),sp2.end());
		// for(auto v:sp1) printf("%lld %lld\n",v[0],v[1]);
		// for(auto v:sp2) printf("%lld %lld\n",v[0],v[1]);
		// puts("");
		for(auto v:sp1)
			g[s][v[0]][v[1]]++,s=f[s][v[0]][v[1]];//,printf("add %lld\n",s);
		for(auto v:sp2)
			g[s][v[0]][v[1]]++,s=f[s][v[0]][v[1]];//,printf("add %lld\n",s);
		// puts("");
	}
	for(int i=30;i>=1;i--)
		for(int u=0;u<=cnt;u++){
			g[u][i-1][0]+=g[u][i][0],g[f[u][i-1][0]][i-1][1]+=g[u][i][0];
			g[u][i-1][1]+=g[u][i][1],g[f[u][i-1][1]][i-1][0]+=g[u][i][1];
		}
	for(int i=0;i<=cnt;i++)
		siz[tr[i][0]]+=g[i][0][0],siz[tr[i][1]]+=g[i][0][1];
	dfs(0);
	for(int i=0;i<t;i++) printf("%lld\n",siz[ed[i]]);
	return 0;
}