#include<bits/stdc++.h>
#define int long long
#define IL inline
#define FOR(i, s, t) for(int i = (s); i <= (t); ++i)
#define ROF(i, s, t) for(int i = (s); i >= (t); --i)
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define mkp make_pair

using namespace std;

const int N = 5e5 + 5;

int n, Q;
int L[N], R[N];
int F[N], zt[N], ct = 0, ids[N];
vector<pii> G, V;

IL void pre(int l, int r, int k, int op) {
    V.clear();
    while(l <= r) {
        while(k > 0 && (r - (1 << k) + 1) < l) k--, op ^= 1;
        int pos = r - (1 << k) + 1;
        V.pb(mkp(k, op)); r = pos - 1; op ^= 1;
    }
    reverse(V.begin(), V.end());
    return;
}

IL void suf(int l, int r, int k, int op) {
    V.clear(); 
    while(l <= r) {
        while(k > 0 && (l + (1 << k) - 1) > r) k--;
        int pos = l + (1 << k) - 1;
        V.pb(mkp(k, op)); l = pos + 1; op ^= 1;
    }
    return;
}

IL void ad() {
    for(pii v : V) G.pb(v); V.clear();
    return;
}

struct ACAM {
    int Trie[N][2], fail[N], tot = 0;
    int f[N][31][2], cc[N][31][2], cnt[N];
    vector<pii> V[N]; 

    IL int insert(string S) {
        int len = S.length(), cur = 0;
        FOR(i, 1, len) {
            int it = (S[i - 1] - '0');
            if(!Trie[cur][it]) Trie[cur][it] = ++tot, V[cur].pb(mkp(Trie[cur][it], it));
            cur = Trie[cur][it];
        }
        return cur;
    }

    IL void build() {
        queue<int> q;
        FOR(i, 0, 1) if(Trie[0][i]) q.push(Trie[0][i]);
        while(!q.empty()) {
            int x = q.front(); q.pop();
            FOR(i, 0, 1) {
                if(!Trie[x][i]) Trie[x][i] = Trie[fail[x]][i];
                else fail[Trie[x][i]] = Trie[fail[x]][i], q.push(Trie[x][i]);
            }
        }
        return;
    }

    IL void buildf() {
        FOR(i, 0, tot) f[i][0][0] = Trie[i][1], f[i][0][1] = Trie[i][0]; 
        FOR(k, 1, 29) {
            FOR(i, 0, tot) {
                f[i][k][0] = f[f[i][k - 1][0]][k - 1][1];
                f[i][k][1] = f[f[i][k - 1][1]][k - 1][0];
            }   
        }
        return;
    }

    IL void print(int x) {
        cout << x << ": ";
        for(pii p : V[x]) cout << p.fi << ' ' << p.se << '\n';
        cout << "fail: " << fail[x] << '\n';
        for(pii p : V[x]) print(p.fi);
        return;
    }

    IL void getres() {
        int cur = 0;
        FOR(i, 1, ct) {
            int t1 = F[i], t2 = zt[i];
            cc[cur][t1][t2]++; cur = f[cur][t1][t2];
            // cout << t1 << ' ' << cur << '\n';
        }
        cnt[cur]++;
        ROF(k, 4, 1) {
            FOR(i, 0, tot) {
                FOR(zt, 0, 1) {
                    // if(i == 7 && k == 1 && zt == 0) cout << cc[i][k][zt] << ' ' << f[i][k - 1][zt] << " ?!!\n";
                    // if(f[i][k - 1][zt] == 6) cout << i << ' ' << k << ' ' << zt << ' ' << cc[i][k][zt] << '\n';
                    cc[i][k - 1][zt] += cc[i][k][zt];
                    cc[f[i][k - 1][zt]][k - 1][zt ^ 1] += cc[i][k][zt];
                }
            }
        }
        // cout << cc[6][0][0] << ' ' << cc[6][0][1] << '\n';
        FOR(i, 0, tot) cnt[i] += cc[i][0][0] + cc[i][0][1];
        // FOR(i, 1, tot) cout << cnt[i] << ' ';
        // cout << '\n';
        ROF(i, tot, 1) cnt[fail[i]] += cnt[i];
        return;
    }
}A;

signed main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> Q;
    FOR(i, 1, n) {
        cin >> L[i] >> R[i];
        int k = 0, op = 0;
        while(true) {
            int l = (1 << k), r = (1 << (k + 1)) - 1;
            if(l < L[i] && r > R[i]) {
                while(true) {
                    k--; int mid = l + (1 << k) - 1;
                    if(R[i] < mid) r = mid;
                    else if(L[i] > mid + 1) l = mid + 1, op ^= 1;
                    else {
                        pre(L[i], mid, k, op); ad();
                        suf(mid + 1, R[i], k, op ^ 1); ad();
                    } 
                }
                break;
            }
            if(r < L[i]) k++;
            else if(l >= L[i] && l <= R[i] && r > R[i]) {
                pre(L[i], l - 1, k - 1, op); ad();
                suf(l, R[i], k, op); ad();
                break;
            }
            else if(l < L[i] && r >= L[i] && r <= R[i]) {
                pre(L[i], r, k, op); ad();
                suf(r + 1, R[i], k + 1, op); ad();
                break;
            }
            else {
                pre(L[i], l - 1, k - 1, op); ad();
                while(r <= R[i]) {
                    G.pb(mkp(k, 0)); k++;
                    if((1 << (k + 1)) - 1 > R[i]) {
                        suf(r + 1, R[i], k, op); ad();
                        break;
                    }
                    l = (1 << k), r = (1 << (k + 1)) - 1;
                } 
                break;
            }
        }
    }
    for(pii p : G) F[++ct] = p.fi, zt[ct] = p.se;
    FOR(i, 1, Q) {
        string S; cin >> S;
        ids[i] = A.insert(S);
    }
    A.build(); A.buildf(); A.getres();
    FOR(i, 1, Q) cout << A.cnt[ids[i]] << '\n';
    return 0;
}

/*
    Author: _LiMLE_
    start coding at: 20:17
    finish debugging at: 
*/