#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

#define int long long

using namespace std;

mt19937 gen(time(0));

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 2e6 + 5, LOG = 22;

int n, m;
int f[N][LOG][2], g[N][LOG][2], pos[N], sum[N];
char str[N];
vc <pii> S;

namespace acam {
	int ch[N][2], fail[N], idx = 1, rt = 1;
	vc <int> G[N];	
	inline int ins (char *s, int n) {
		int x = rt;
		for (int i = 1, c; i <= n; i++, x = ch[x][c]) 
			if (!ch[x][c = s[i] - '0']) ch[x][c] = ++idx;
		return x;
	}
	inline void build () {
		queue <int> Q;
		rep (i, 0, 1) 
			if (ch[rt][i]) fail[ch[rt][i]] = rt, Q.push (ch[rt][i]); 
			else ch[rt][i] = rt;
		while (!Q.empty ()) {
			int x = Q.front (); Q.pop ();
			rep (i, 0, 1) 
				if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], Q.push (ch[x][i]);
				else ch[x][i] = ch[fail[x]][i];
		}
		rep (i, 2, idx) G[fail[i]].pb (i);
	}
	inline void dfs (int x) {
		sum[x] += g[x][0][0] + g[x][0][1];
		for (auto y : G[x]) dfs (y), sum[x] += sum[y];
	}
}
using namespace acam;

inline void collect (int l, int r, int L, int R, int d, int s = 0) {
	if (L > R || L > r || R < l) return ;
	if (L <= l && R >= r) return S.pb (mkp (d, s)), void ();
	int mid = l + r >> 1;
	collect (l, mid, L, R, d - 1, s); collect (mid + 1, r, L, R, d - 1, s ^ 1);
}

signed main() {
	n = read(); m = read(); 
	
	for (int i = 1, l, r; i <= n; i++) 
		l = read(), r = read(), collect (0, (1ll << 31) - 1, l, r, 31);
	
	for (int i = 1, l; i <= m; i++) {
		scanf ("%s", str + 1); l = strlen (str + 1);
		pos[i] = ins (str, l);
	}
	acam :: build ();
	
	rep (i, 1, idx) rep (j, 0, 1) f[i][0][j] = ch[i][j];
	rep (i, 1, LOG - 1) rep (x, 1, idx) rep (j, 0, 1) 
		f[x][i][j] = f[f[x][i - 1][j]][i - 1][1 - j];
	// match 
	{
		int x = rt; 
		for (auto [u, v] : S) ++g[x][u][v], x = f[x][u][v];
		++sum[x];
	}
	lep (i, LOG - 1, 1) rep (x, 1, idx) rep (j, 0, 1) 
		g[x][i - 1][j] += g[x][i][j], g[f[x][i - 1][j]][i - 1][1 - j] += g[x][i][j];
	dfs (rt);
	
	rep (i, 1, m) printf ("%lld\n", sum[pos[i]]);
	
	return 0;
}