#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , L = 5e5 + 5 , LG = 30 , C = 2;
int n , q , l[N] , r[N] , ans[N]; string s[N];
namespace ACAM
{
	int tot , tr[L][C] , fail[L] , *fa = fail;
	int f[L][LG][2]; ll g[L][LG][2] , cnt[L];
	vector<int>vc[L] , e[L];
	void insert(const string &s , int i)
	{
		int p = 0;
		for(int c : s)
		{
			int &v = tr[p][c - '0'];
			if(!v)v = ++tot;
			p = v;
		}
		vc[p].push_back(i);
	}
	void dfs(int u)
	{
		for(int v : e[u])
		{
			dfs(v);
			cnt[u] += cnt[v];
		}
		for(int i : vc[u])
			ans[i] = cnt[u];
	}
	void build()
	{
		queue<int>q;
		for(int i = 0 ; i < C ; i++)
			if(tr[0][i])q.push(tr[0][i]);
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			for(int i = 0 ; i < C ; i++)
			{
				int &v = tr[u][i] , &w = tr[fail[u]][i];
				if(!v)v = w;
				else fail[v] = w , q.push(v);
			}
		}
	}
	void calc()
	{
		for(int i = 0 ; i <= tot ; i++)
		{
			f[i][0][0] = tr[i][0];
			f[i][0][1] = tr[i][1];
		}
		for(int j = 1 ; j < LG ; j++)
			for(int i = 0 ; i <= tot ; i++)
				for(int k = 0 ; k <= 1 ; k++)
					f[i][j][k] = f[f[i][j - 1][k]][j - 1][k ^ 1];
		auto low = [&](int x){return x & -x;};
		auto high = [&](int x){return 1 << (31 - __builtin_clz(x));};
		auto pop = [&](int x){return __builtin_popcount(x);};
		for(int i = 1 , p = 0 ; i <= n ; i++)
		{
			int l = ::l[i] , r = ::r[i] + 1;
			while(high(l) != high(r))
			{
				int k = __lg(low(l));
				int t = pop(l >> k) & 1;
				g[p][k][t]++;
				p = f[p][k][t];
				l += low(l);
			}
			for(int x = r - l ; x ; x -= high(x))
			{
				int k = __lg(high(x));
				int t = pop(l >> k) & 1;
				g[p][k][t]++;
				p = f[p][k][t];
				l += high(x);
			}
		}
		for(int j = LG - 1 ; j >= 1 ; j--)
			for(int i = 0 ; i <= tot ; i++)
				for(int k = 0 ; k <= 1 ; k++)
				{
					g[i][j - 1][k] += g[i][j][k];
					g[f[i][j - 1][k]][j - 1][k ^ 1] += g[i][j][k];
				}
		for(int i = 0 ; i <= tot ; i++)
			for(int k = 0 ; k <= 1 ; k++)
				cnt[f[i][0][k]] += g[i][0][k];
		for(int u = 1 ; u <= tot ; u++)
			e[fa[u]].push_back(u);
		dfs(0);
	}
}
int main()
{
	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++)
	{
		cin >> s[i];
		ACAM::insert(s[i] , i);
	}
	ACAM::build();
	ACAM::calc();
	for(int i = 1 ; i <= q ; i++)
		cout << ans[i] << "\n";
	return 0;
}