#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 5e5 + 5;
int q, trie[N][2], tot = 1, fail[N], f[N][30][2], g[N][30][2], occ[N];
vector<int> vec[N], son[N];
void insert(string s, int id) {
	int now = 1;
	for (char c : s) {
		int &nxt = trie[now][c - '0'];
		if (!nxt) nxt = ++tot;
		now = nxt;
	}
	vec[now].push_back(id);
}
void build() {
	queue<int> Q;
	for (int i : {0, 1}) {
		if (trie[1][i]) {
			fail[trie[1][i]] = 1;
			Q.push(trie[1][i]);
		} else {
			trie[1][i] = 1;
		}
	}
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int i : {0, 1}) {
			if (trie[u][i]) {
				fail[trie[u][i]] = trie[fail[u]][i];
				Q.push(trie[u][i]);
			} else {
				trie[u][i] = trie[fail[u]][i];
			}
		}
	}
	for (int i = 2; i <= tot; i++) {
		son[fail[i]].push_back(i);
	}
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n >> q;
	vector<array<int, 2>> seg;
	for (int i = 0, l, r; i < n; i++) {
		cin >> l >> r;
		auto check = [&](int k) {
			if (l + (1 << k) - 1 > r || l % (1 << k)) return;
			seg.push_back({k, __builtin_parity(l)});
			l += (1 << k);
		};
		for (int k = 0; k < 30; k++) {
			check(k);
			check(k);
		}
		for (int k = 29; k >= 0; k--) {
			check(k);
		}
	}
	for (int i = 0; i < q; i++) {
		string s;
		cin >> s;
		insert(s, i);
	}
	build();
	for (int i = 1; i <= tot; i++) {
		for (int j : {0, 1}) {
			f[i][0][j] = trie[i][j];
		}
	}
	for (int k = 1; k < 30; k++) {
		for (int i = 1; i <= tot; i++) {
			for (int j : {0, 1}) {
				f[i][k][j] = f[f[i][k - 1][j]][k - 1][!j];
			}
		}
	}
	int now = 1;
	for (auto [k, v] : seg) {
		g[now][k][v]++;
		now = f[now][k][v];
	}
	for (int k = 28; k >= 0; k--) {
		for (int i = 1; i <= tot; i++) {
			for (int j : {0, 1}) {
				g[i][k][j] += g[i][k + 1][j];
				g[f[i][k][j]][k][!j] += g[i][k + 1][j];
			}
		}
	}
	for (int i = 1; i <= tot; i++) {
		occ[trie[i][0]] += g[i][0][0];
		occ[trie[i][1]] += g[i][0][1];
	}
	vector<int> ans(q);
	function<void(int)> dfs = [&](int u) {
		for (int v : son[u]) {
			dfs(v);
			occ[u] += occ[v];
		}
		for (int i : vec[u]) {
			ans[i] = occ[u];
		}
	};
	dfs(1);
	for (int x : ans) {
		cout << x << "\n";
	}
	return 0;
}