// 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define wr(x,ch) write(x),putchar(ch)
using namespace std;
const int N=500005;
ll read() {
    ll x=0;bool f=0;char c=getchar();
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
void write(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar(x%10^48);
    return ;
}
int m,n,l,r;
char t[N];
struct str {
	int x,y;
}a[N*30];
struct Others {
	struct node {
		int tag[31][2],to[31][2],fail,ch[2];
	}tr[N];int tot,repos[N],sum[N];
	vector<int> G[N];
	void insert(char *s,int len,int id) {
		int p=0;
		for(int i=1;i<=len;i++) {
			if(!tr[p].ch[s[i]-'0']) tr[p].ch[s[i]-'0']=++tot;
			p=tr[p].ch[s[i]-'0'];
		}
		repos[id]=p;
		return ;
	}
	void build() {
		queue<int> qu;
		if(tr[0].ch[0]) qu.push(tr[0].ch[0]);
		if(tr[0].ch[1]) qu.push(tr[0].ch[1]);
		while(qu.size()) {
			int p=qu.front();qu.pop();
			if(tr[p].ch[0]) tr[tr[p].ch[0]].fail=tr[tr[p].fail].ch[0],qu.push(tr[p].ch[0]);
			else tr[p].ch[0]=tr[tr[p].fail].ch[0];
			if(tr[p].ch[1]) tr[tr[p].ch[1]].fail=tr[tr[p].fail].ch[1],qu.push(tr[p].ch[1]);
			else tr[p].ch[1]=tr[tr[p].fail].ch[1];
		}
		for(int i=1;i<=tot;i++) G[tr[i].fail].push_back(i);
		for(int i=0;i<=tot;i++) tr[i].to[0][0]=tr[i].ch[0],tr[i].to[0][1]=tr[i].ch[1];
		for(int i=1;i<=30;i++) 
			for(int j=0;j<=tot;j++) 
				tr[j].to[i][0]=tr[tr[j].to[i-1][0]].to[i-1][1],
				tr[j].to[i][1]=tr[tr[j].to[i-1][1]].to[i-1][0];
		return ;
	}
	void solve() {
		for(int i=30;i>0;i--) {
			for(int j=0;j<=tot;j++) {
				int t=tr[j].tag[i][0];
				tr[tr[j].to[i-1][0]].tag[i-1][1]+=t;
				tr[j].tag[i-1][0]+=t;
				t=tr[j].tag[i][1];
				tr[tr[j].to[i-1][1]].tag[i-1][0]+=t;
				tr[j].tag[i-1][1]+=t;
			}
		}
		for(int j=0;j<=tot;j++) 
			sum[tr[j].ch[0]]+=tr[j].tag[0][0],sum[tr[j].ch[1]]+=tr[j].tag[0][1];
		for(int i=0;i<=tot;i++) {
//			printf("%d %d %d\n",i,tr[i].ch[0],0);
//			printf("%d %d %d\n",i,tr[i].ch[1],1);
//			printf("%d:%d %d\n",i,tr[i].ch[0],tr[i].ch[1]);
		}
		dfs(0);
		return ;
	}
	void dfs(int p) {
		for(const auto &lxl:G[p]) dfs(lxl),sum[p]+=sum[lxl];
		return ;
	}
}T;
signed main() {
	m=read();int mm=read();
	for(int i=1;i<=m;i++) {
		l=read(),r=read();
		int s=-1;
		int tn=n;
		for(int j=0;j<=30;j++) 
			if(l>>j&1) {
				if(l+(1<<j)>r) {
					s=j;
					break;
				}
				int t=0;
				for(int k=j;k<=30;k++) t+=(l>>k&1);
				a[++n]=(str){j,t&1};
				l+=(1<<j);
			}
		reverse(a+tn+1,a+n+1);
		for(int j=s-1;j>=0;j--) {
			if(r>>j&1) {
				int t=0;
				for(int k=j+1;k<=30;k++) t+=(r>>k&1);
				a[++n]=(str){j,t&1};
			}
		}
		int t=0;
		for(int j=0;j<=30;j++) t+=(r>>j&1);
		a[++n]=(str){0,t&1};
	}
	m=mm;
	for(int i=1;i<=m;i++) {
		scanf("%s",t+1);
		T.insert(t,strlen(t+1),i);
	}
	T.build();
	int p=0;
//	for(int i=1;i<=n;i++) printf("(%d,%d) ",a[i].x,a[i].y);puts("");
	for(int i=1;i<=n;i++) {
		T.tr[p].tag[a[i].x][a[i].y]++;
		p=T.tr[p].to[a[i].x][a[i].y];
	}
	T.solve();
	for(int i=1;i<=m;i++) wr(T.sum[T.repos[i]],'\n');
	return 0;
}