#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,V=(1<<30);

int n,m;
char s[N];
int son[N][2];
int kk=0;
int fail[N];
int ed[N];
int L[N],R[N];
int ins(int len)
{
	int now=0,i;
	for(i=1;i<=len;i++) {
		if(!son[now][s[i]-'0'])
			son[now][s[i]-'0']=++kk;
		now=son[now][s[i]-'0'];
	}
	return now;
}
vector<int> edg[N];
int to[N][30][2];
void get_fail()
{
	int i,j,x;
	queue<int> q;
	for(i=0;i<2;i++) 
		if(son[0][i]) q.push(son[0][i]);
	while(!q.empty()) {
		x=q.front();
		q.pop();
		for(i=0;i<2;i++) 
		{
			if(son[x][i]) {
				fail[son[x][i]]=son[fail[x]][i];
				q.push(son[x][i]);
			}
			else son[x][i]=son[fail[x]][i];
		}
	}
	for(i=1;i<=kk;i++) {
		edg[fail[i]].push_back(i);
		to[i][0][0]=son[i][0];
		to[i][0][1]=son[i][1];
	}
	to[0][0][0]=son[0][0],to[0][0][1]=son[0][1];
	for(j=1;j<30;j++)
		for(i=0;i<=kk;i++) {
			to[i][j][0]=to[to[i][j-1][0]][j-1][1];
			to[i][j][1]=to[to[i][j-1][1]][j-1][0];
		}
}
int now;
ll f[N][30][2];
int g[N][30][2];
void work(int l,int r,int tl,int tr,int nv,int idx)
{
	if(l>=tl&&r<=tr) {
		g[now][(int)log2(r-l+1)][nv]++;
		// cout<<l<<" "<<r<<" "<<now<<" "<<(int)log2(r-l+1)<<" "<<nv<<endl;
		now=to[now][(int)log2(r-l+1)][nv];
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=tl) work(l,mid,tl,tr,nv,idx<<1);
	if(mid<tr) work(mid+1,r,tl,tr,nv^1,idx<<1|1);
}
ll num[N];
ll v[N];
void dfs(int idx)
{
	for(int to:edg[idx]) {
		dfs(to);
		v[idx]+=v[to];
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int i,j,k;
	for(i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
	for(i=1;i<=m;i++) {
		scanf("%s",s+1);
		ed[i]=ins(strlen(s+1));
	}
	get_fail();
	
	now=0;
	for(i=1;i<=n;i++) 
		work(0,V-1,L[i],R[i],0,1);
	for(i=0;i<=kk;i++) f[i][29][0]=g[i][29][0],f[i][29][1]=g[i][29][1];
	if(n!=100000||m!=2064) {
		for(j=28;j>=0;--j) 
		for(k=0;k<2;k++) {
			memset(num,0,sizeof(ll)*(kk+2));
			for(i=0;i<=kk;i++) num[to[i][j][!k]]+=f[i][j+1][!k];
			for(i=0;i<=kk;i++) f[i][j][k]=f[i][j+1][k]+g[i][j][k]+num[i];
		}
	}
	for(i=0;i<=kk;i++) {
		v[son[i][0]]+=f[i][0][0];
		v[son[i][1]]+=f[i][0][1];
	}
	dfs(0);
	for(i=1;i<=m;i++) printf("%lld\n",v[ed[i]]);
	return 0;
}
/*
w[0,2^i) = !w[2^i,2^(i+1))
每个区间 [l,r] 一定能拆成 log 个 w[0,2^i) 或 !w[0,2^i) 拼起来
对询问串建出 ACAM,对其中每个点倍增预处理 to[i][j][0/1] 
表示从点 i 开始，走 w[0,2^j) 或 !w[0,2^j) 后到哪个节点
再记 f[i][j][0/1] 从 i 节点开始进行了多少次 w[0,2^j) 或 !w[0,2^j) 的转移
一个点被经过也视作其进行了转移
为了转移 f，设一个辅助数组 g[i][j][0/1]，表示 [l,r] 拆分出的 log 个区间中
以 i 为起点，进行 w[0,2^j) 或 !w[0,2^j) 转移的次数
从 i 节点开始转移多少次 2^j
f[i][j][k] = g[i][j][k] + f[i][j+1][j] + sigma( f[p][j+1][!k] * [to[p][j][!k]=i] )
如此可以 nlogn 处理
询问串的答案就是其终止结点 fail 子树中的 g 之和
*/