#include <bits/stdc++.h>
#define LL long long
#define mes(s, x) memset(s, x, sizeof(s))
#define Maxn 100005
#define Maxl 500005
using namespace std;
inline LL read(){char c;c = getchar();while(!(('0' <= c && c <= '9') || c == '-')) c = getchar();bool flag = 0;if(c == '-'){flag = 1;c = getchar();}LL tot = 0;while('0' <= c && c <= '9'){tot = 10 * tot + c - '0';c = getchar();}return flag ? -tot : tot;}
int L[Maxn], R[Maxn];
char s[Maxn];
int id[Maxn], tr[Maxl][2], nxt[Maxl][30][2], cnt, fail[Maxl], px;
LL x[Maxl][30][2], ans[Maxl];
vector<int> g[Maxl];
void insert(int l, int x){
    int p = 0, c;
    for(int i = 1; i <= l; i++){
        c = s[i] - '0';
        if(!tr[p][c]) tr[p][c] = ++cnt;
        p = tr[p][c];
    }
    id[x] = p;
}
void build(){
    queue<int> q;
    for(int i = 0; i < 2; i++) if(tr[0][i]) q.push(tr[0][i]);
    int x;
    while(q.size()){
        x = q.front();
        q.pop();
        g[fail[x]].push_back(x);
        for(int i = 0; i < 2; i++){
            if(tr[x][i]){
                fail[tr[x][i]] = tr[fail[x]][i];
                q.push(tr[x][i]);
            }else tr[x][i] = tr[fail[x]][i];
        }
    }
    for(int i = 0; i <= cnt; i++) nxt[i][0][0] = tr[i][0], nxt[i][0][1] = tr[i][1];
    for(int i = 1; i < 30; i++){
        for(int j = 0; j <= cnt; j++){
            nxt[j][i][0] = nxt[nxt[j][i - 1][0]][i - 1][1];
            nxt[j][i][1] = nxt[nxt[j][i - 1][1]][i - 1][0];
        }
    }
}
void add(int i, int k){
    x[px][i][k]++;
    px = nxt[px][i][k];
}
void dfs(int i){
    ans[i] = x[i][0][0] + x[i][0][1];
    assert(ans[i] > 1e9);
    int o;
    for(int j = 0; j < g[i].size(); j++){
        o = g[i][j];
        dfs(o);
        ans[i] += ans[o];
    }
}
int popcnt(int i){
    int t = 0;
    while(i){
        t++;
        i &= i - 1;
    }
    return t;
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    int n = read(), m = read();
    for(int i = 1; i <= n; i++) L[i] = read(), R[i] = read() + 1;
    for(int i = 1; i <= m; i++){
        scanf("%s", s + 1);
        insert(strlen(s + 1), i);
    }
    build();
    int flag;
    for(int i = 1; i <= n; i++){
        flag = 1;
        for(int j = 29; j >= 0; j--){
            if(((L[i] >> j) & 1) < ((R[i] >> j) & 1)){
                for(int k = 0; k < j; k++){
                    if((L[i] >> k) & 1){
                        add(k, popcnt(L[i]) % 2);
                        L[i] += 1 << k;
                    }
                }
                if(!((L[i] >> j) & 1)){
                    add(j, popcnt(L[i]) % 2);
                    L[i] += 1 << j;
                }
                for(int k = j - 1; k >= 0; k--){
                    if((R[i] >> k) & 1){
                        add(k, popcnt(L[i]) % 2);
                        L[i] += 1 << k;
                    }
                }
            }
        }
    }
    for(int i = 29; i >= 1; i--){
        for(int j = 0; j <= cnt; j++){
            for(int k = 0; k < 2; k++){
                x[j][i - 1][k] += x[j][i][k];
                x[nxt[j][i - 1][k]][i - 1][k ^ 1] += x[j][i][k];
            }
        }
    }
    x[px][0][0]++;
    dfs(0);
    for(int i = 1; i <= m; i++) printf("%lld\n", ans[id[i]]);
    return 0;
}