#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second 
#define pb push_back
#define mk make_pair 
using namespace std;
const int MAXN = 1e5 + 5, MAXM = 5e5 + 5, M = 30;

int k[M * 2], p[M * 2];
int n, q, root, cnt, m;
int son[MAXM][2], fail[MAXM], id[MAXM];
ll Ans[MAXM], g[2][M + 1][MAXM];
int f[2][M][MAXM], sum[2][M][MAXM];
char str[MAXM];

void dfs(int ql, int qr, int l, int r) {
	int mid = (l + r) >> 1;
    if (l >= qr || r <= ql) return;
    if (l >= ql && r <= qr){
        k[m] = 31 - __builtin_clz(r - l), p[m] = __builtin_parity(l >> k[m]);
        m ++;
        return;
    }
    dfs(ql, qr, l, mid), dfs(ql, qr, mid, r);
}

int l[MAXM], r[MAXM];
int que[MAXM];

struct Trie {
	int Insert(int len, char s[], int &pos) {
	    for (int i = 0; i < len; i ++){
	        int c = s[i] - '0';
	        if (!son[pos][c]) son[pos][c] = ++ cnt;
	        pos = son[pos][c];
	    }
	}
	void Build() {
		int L = 0, R = 0;
	    fail[root] = root;
	    for (int j = 0; j <= 1; j ++){
	        if (son[root][j]){
	            fail[son[root][j]] = root;
	            que[R ++] = son[root][j];
	        }
			else son[root][j] = root;
	    }
	    while (L < R){
	        int u = que[L]; L ++;
	        for (int j = 0; j <= 1; j ++){
	            if (son[u][j]){
	                fail[son[u][j]] = son[fail[u]][j];
	                que[R ++] = son[u][j];
	            } 
				else son[u][j] = son[fail[u]][j];
	        }
	    }
	} 
	void get() {
		int pos = 0;
	    for (int i = 1; i <= n; i ++){
	        m = 0; 
			dfs(l[i], r[i] + 1, 0ll, 1ll << 30);
	        for (int j = 0; j < m; j ++){
	            sum[p[j]][k[j]][pos] ++;
	            pos = f[p[j]][k[j]][pos];
	        }
	    }
	}
} t;

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> l[i] >> r[i];
    for (int i = 1; i <= q; i ++){
        scanf("%s", str);
        t.Insert(strlen(str), str, id[i]);
    }
    t.Build();
    for (int i = 0; i <= cnt; i ++) f[0][0][i] = son[i][0], f[1][0][i] = son[i][1];
    for (int j = 1; j < M; j ++){
    	for (int i = 0; i <= cnt; i ++){
            f[0][j][i] = f[1][j - 1][f[0][j - 1][i]];
            f[1][j][i] = f[0][j - 1][f[1][j - 1][i]];
        }
	}
	t.get();
    for (int j = M - 1; j >= 0; j --){
    	for (int i = 0; i <= cnt; i ++){
            g[0][j][i] += sum[0][j][i] + g[0][j + 1][i];
            g[1][j][i] += sum[1][j][i] + g[1][j + 1][i];
            g[1][j][f[0][j][i]] += g[0][j + 1][i];
            g[0][j][f[1][j][i]] += g[1][j + 1][i];
        }
	}
    for (int i = 0; i <= cnt; i ++){
        Ans[son[i][0]] += g[0][0][i];
        Ans[son[i][1]] += g[1][0][i];
    }
    for (int i = cnt; i >= 0; i --) Ans[fail[que[i]]] += Ans[que[i]];
    for (int i = 1; i <= q; i ++) printf("%lld\n", Ans[id[i]]);
    return 0;
}