// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
const int N = 5e5 + 10;
int n, m, l[N], r[N], t[N][2], fail[N], tot, id[N], jump[31][N][2];
ll ans[N][31][2], occ[N];
int ins() {
	string st; cin >> st;
	int x = 0;
	for (char i: st) {
		int k = i == '1';
		if (!t[x][k]) t[x][k] = ++tot;
		x = t[x][k];
	}
	return x;
}
vector <int> g[N];
void build() {
	queue <int> q;
	F(i, 0, 1)
		if (t[0][i]) q.push(t[0][i]);
	while (q.size()) {
		int x = q.front(); q.pop();
		F(i, 0, 1)
			if (t[x][i]) {
				fail[t[x][i]] = t[fail[x]][i];
				q.push(t[x][i]);
			} else t[x][i] = t[fail[x]][i];//, debug << fail[x] << " " << i << endl;
	}
	F(i, 1, tot) g[fail[i]].push_back(i);
	// F(i, 0, tot)
	// 	F(j, 0, 1)
	// 		cout << i << ' ' << j << ' ' << ' ' << t[i][j] << '\n';
	F(i, 0, tot)
		F(j, 0, 1)
			jump[0][i][j] = t[i][j];
	F(i, 1, 30)
		F(j, 0, tot)
			F(k, 0, 1)
				jump[i][j][k] = jump[i - 1][jump[i - 1][j][k]][k ^ 1];
}
void update() {
	DF(i, 30, 1)
		F(j, 0, tot)
			F(k, 0, 1) {
				ans[i - 1][j][k] += ans[i][j][k];
				ans[i - 1][jump[i - 1][j][k]][k ^ 1] += ans[i][j][k];
			}
	F(i, 0, tot)
		F(j, 0, 1)
			occ[t[i][j]] += ans[0][i][j];
}
void dfs(int x) {
	for (int i: g[x]) dfs(i), occ[x] += occ[i];
}
signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;
	F(i, 1, n) cin >> l[i] >> r[i];
	F(i, 1, m) id[i] = ins();
	build();
	int x = 0;
	F(i, 1, n)
		while (l[i] <= r[i]) {
			int t = l[i] & -l[i];
			while (l[i] + t - 1 > r[i]) t /= 2;
			// debug << x << " " << __builtin_ctz(t) << endl;
			ans[__builtin_ctz(t)][x][__builtin_parity(l[i])]++;
			x = jump[__builtin_ctz(t)][x][__builtin_parity(l[i])];
			l[i] += t;
		}
	update();
	dfs(0);
	F(i, 1, m) cout << occ[id[i]] << '\n';
	return 0;
}
/* why?
3 1
2 6
1 3
4 8
0
*/