#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10,M=32;
int tr[N][2],idx;
int Id[N];
int ne[N];
int L[N],R[N];
int f[N][M][2];
LL g[N][M][2];
LL sum[N];
int n,m;

void insert(string s,int x)
{
	int u=1;
	for(int i=0;i<s.size();i++)
	{
		int c=s[i]-'0';
		if(!tr[u][c]) tr[u][c]=++idx;
		u=tr[u][c];
	}
	Id[x]=u;
}

int q[N],hh=0,tt=-1;
void build()
{
	for(int c=0;c<2;c++) if(tr[1][c]) q[++tt]=tr[1][c],ne[tr[1][c]]=1;
	while(hh<=tt)
	{
		int u=q[hh++];
		//printf("[%d]\n",u); 
		for(int c=0;c<2;c++)
		{
			int &v=tr[u][c];
			if(!v) v=tr[ne[u]][c];
			else ne[v]=tr[ne[u]][c],q[++tt]=v;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>L[i]>>R[i];
	idx=1;
	for(int i=1;i<=m;i++)
	{
		string s;
		cin>>s;
		insert(s,i);
	}
	
	build();
	
	//exit(0);
	
	for(int u=1;u<=idx;u++)
	{
		f[u][0][0]=tr[u][0],f[u][0][1]=tr[u][1];
	}
	for(int j=1;j<M;j++)
	{
		for(int u=1;u<=idx;u++)
		{
			f[u][j][0]=f[f[u][j-1][0]][j-1][1];
			f[u][j][1]=f[f[u][j-1][1]][j-1][0];	
		}
	}
	
	int u=1;
	for(int i=1;i<=n;i++)
	{
		int l=L[i],r=R[i];
		while(l<=r)
		{
			int sz=__builtin_popcount(l),j=min(__builtin_ctz(l),__lg(r-l+1)); 
			g[u][j][sz&1]++,u=f[u][j][sz&1];
			l+=(1<<j);
		}
	} 
	
	for(int j=M-1;j>=1;j--)
	{
		for(int u=1;u<=idx;u++)
		{
			g[u][j-1][0]+=g[u][j][0],g[f[u][j-1][0]][j-1][1]+=g[u][j][0];
			g[u][j-1][1]+=g[u][j][1],g[f[u][j-1][1]][j-1][0]+=g[u][j][1];
		}
	}
	
	for(int u=1;u<=idx;u++) sum[tr[u][0]]+=g[u][0][0],sum[tr[u][1]]+=g[u][0][1];
	
	for(int i=idx-1;i>=0;i--)
	{
		int u=q[i];
		//printf("[%d %d]\n",u,ne[u]);
		sum[ne[u]]+=sum[u];
	}
	
	for(int i=1;i<=m;i++) cout<<sum[Id[i]]<<"\n";
	
	return 0;
}