#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
int n, q, tcnt, l[N], r[N];
int cnt, siz[N], flg[N];
void solve(int l, int r, int ql, int qr) {
	int mid = l + r >> 1;
	if(ql <= l && r <= qr) {
		int k = 31 - __builtin_clz(r - l), p = l >> k;
		cnt++, siz[cnt] = k, flg[cnt] = __builtin_popcount(p) & 1; 
		return;
	}
	if(ql < mid) solve(l, mid, ql, qr);
    if(mid < qr) solve(mid, r, ql, qr);
}
struct node {int son[2], fail;} trie[N];
int pos[N];
int insert(char* s) {
	int len = strlen(s), u = 0;
	for(int i = 0; i < len; i++) {
		int v = s[i] - '0';
		if(!trie[u].son[v]) trie[u].son[v] = ++tcnt;
		u = trie[u].son[v];
	}
	return u;
}
void build() {
	queue<int> q;
	for(int i = 0; i < 2; i++) if(trie[0].son[i]) q.push(trie[0].son[i]);	
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = 0; i < 2; i++) {
			if(trie[u].son[i]) trie[trie[u].son[i]].fail = trie[trie[u].fail].son[i], q.push(trie[u].son[i]);
			else trie[u].son[i] = trie[trie[u].fail].son[i];
		} 
	}
}
int f[N][30][2], g[N][30][2], c[N][30][2];
ll ans[N];
signed main() {
#ifdef ddxrS
	freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>q;
	for(int i = 1; i <= n; i++) cin>>l[i]>>r[i];
	for(int i = 1; i <= q; i++) {
		char s[N]; cin>>s;
		pos[i] = insert(s);
	}
	build();
	for(int i = 0; i <= tcnt; i++) f[i][0][0] = trie[i].son[0], f[i][0][1] = trie[i].son[1];
	for(int j = 1; j < 30; j++) for(int i = 0; i <= tcnt; i++)
		f[i][j][0] = f[f[i][j - 1][0]][j - 1][1], f[i][j][1] = f[f[i][j - 1][1]][j - 1][0];
	for(int i = 1, u = 0; i <= n; i++) {
		cnt = 0, solve(0, 1 << 30, l[i], r[i] + 1);
		for(int j = 1; j <= cnt; j++) c[u][siz[j]][flg[j]]++, u = f[u][siz[j]][flg[j]];
	}
	for(int j = 29; j >= 0; j--) for(int i = 0; i <= tcnt; i++)
        g[i][j][0] += c[i][j][0] + g[i][j + 1][0], g[i][j][1] += c[i][j][1] + g[i][j + 1][1], 
        g[f[i][j][0]][j][1] += g[i][j + 1][0], g[f[i][j][1]][j][0] += g[i][j + 1][1];
	for(int i = 0; i <= tcnt; i++) ans[trie[i].son[0]] += g[i][0][0], ans[trie[i].son[1]] += g[i][0][1];
	for(int i = tcnt; i >= 1; i--) ans[trie[i].fail] += ans[i];
	for(int i = 1; i <= q; i++) cout<<ans[pos[i]]<<'\n';
	cerr<<clock() * 1.0 / CLOCKS_PER_SEC<<'\n';
	return 0;
}