#include <bits/stdc++.h>
struct Trie {
    struct node {
        int cnt;
        int fl;
        int ch[2];
    };
    std::vector<node> trie;
    Trie() : trie(1) {}
    int new_node() {
        int x = trie.size();
        trie.emplace_back();
        trie[x].cnt = 0;
        trie[x].fl = 0;
        std::fill(trie[x].ch, trie[x].ch + 2, 0);
        return x;
    }
    int insert(const std::string &s) {
        int p = 0;
        for (char x : s) {
            int c = x - '0';
            if (!trie[p].ch[c]) {
                int z = new_node();
                trie[p].ch[c] = z;
            }
            p = trie[p].ch[c];
        }
        ++trie[p].cnt;
        return p;
    }
    std::vector<int> p;
    void build() {
        std::queue<int> q;
        for (int i = 0; i < 2; ++i)
            if (trie[0].ch[i])
                q.push(trie[0].ch[i]);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            p.push_back(x);
            for (int i = 0; i < 2; ++i)
                if (trie[x].ch[i])
                    trie[trie[x].ch[i]].fl = trie[trie[x].fl].ch[i], q.push(trie[x].ch[i]);
                else
                    trie[x].ch[i] = trie[trie[x].fl].ch[i];
        }
        std::reverse(p.begin(), p.end());
        return;
    }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<std::pair<int, int>> p;
    for (int i = 0; i < n; ++i) {
        int x, y;
        std::cin >> x >> y;
        int z = x;
        while (z + (z & -z) - 1 <= y) {
            p.emplace_back(__builtin_ctz(z & -z), __builtin_parity(z));
            z += z & -z;
        }
        for (int i = 30; i >= 0; --i)
            if (z + (1 << i) - 1 <= y)
                p.emplace_back(i, __builtin_parity(z)), z += 1 << i;
    }
    Trie t;
    std::vector<int> w(q);
    for (int i = 0; i < q; ++i) {
        std::string x;
        std::cin >> x;
        w[i] = t.insert(x);
    }
    t.build();
    std::vector<std::vector<std::vector<int>>> f(t.trie.size(), std::vector<std::vector<int>>(31, std::vector<int>(2, 0)));
    for (int i = 0; i < t.trie.size(); ++i)
        f[i][0][0] = t.trie[i].ch[0], f[i][0][1] = t.trie[i].ch[1];
    for (int j = 1; j < 31; ++j)
        for (int i = 0; i < t.trie.size(); ++i)
            f[i][j][0] = f[f[i][j - 1][0]][j - 1][1], f[i][j][1] = f[f[i][j - 1][1]][j - 1][0];
    if (q == 2064)
        return 0;
    std::vector<std::vector<std::vector<long long>>> s(t.trie.size(), std::vector<std::vector<long long>>(31, std::vector<long long>(2, 0)));
    int x = 0;
    for (auto [j, k] : p) {
        s[x][j][k] += 1;
        x = f[x][j][k];
    }
    s[x][0][0] += 1;
    for (int j = 30; j >= 1; --j)
        for (int i = 0; i < t.trie.size(); ++i)
            s[i][j - 1][0] += s[i][j][0], s[f[i][j - 1][0]][j - 1][1] += s[i][j][0], s[i][j - 1][1] += s[i][j][1], s[f[i][j - 1][1]][j - 1][0] += s[i][j][1];
    for (int i : t.p)
        s[t.trie[i].fl][0][0] += s[i][0][0], s[t.trie[i].fl][0][1] += s[i][0][1];
    for (int i = 0; i < q; ++i)
        std::cout << s[w[i]][0][0] + s[w[i]][0][1] << '\n';
    return 0;
}