#include <vector>
#include <iostream>

using namespace std;
using LL = long long;
using S = pair<int, bool>;

const int kN = 1e5 + 1, kT = 5e5 + 1;
const int kL = 30;

struct E {
  int n[kL][2], f;
  LL t[kL][2], c;
} e[kT];
int n, q, c, p[kN];
vector<S> s;
int d[kN], h = 1, t;

void A(int k, bool rv, int l, int r, int tl, int tr) {
  if (l == tl && r == tr) {
    s.emplace_back(k, rv);
    return;
  }
  int m = l + (1 << k - 1) - 1;
  if (tl <= m) {
    A(k - 1, rv, l, m, tl, min(m, tr));
  }
  if (m < tr) {
    A(k - 1, !rv, m + 1, r, max(m + 1, tl), tr);
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for (int i = 1, l, r; i <= n; ++i) {
    cin >> l >> r;
    A(kL, 0, 0, (1 << kL) - 1, l, r);
  }
  for (int i = 1; i <= q; ++i) {
    string t;
    cin >> t;
    int x = 0;
    for (char ch : t) {
      int &y = e[x].n[0][ch - '0'];
      if (!y) {
        y = ++c;
      }
      x = y;
    }
    p[i] = x;
  }
  for (d[++t] = 0; h <= t; ++h) {
    int x = d[h];
    for (int i = 0; i < 2; ++i) {
      int &y = e[x].n[0][i];
      if (y) {
        e[y].f = (x ? e[e[x].f].n[0][i] : 0);
        d[++t] = y;
      } else {
        y = e[e[x].f].n[0][i];
      }
    }
  }
  for (int i = 0; i < kL - 1; ++i) {
    for (int x = 0; x <= c; ++x) {
      e[x].n[i + 1][0] = e[e[x].n[i][0]].n[i][1];
      e[x].n[i + 1][1] = e[e[x].n[i][1]].n[i][0];
    }
  }
  int x = 0;
  for (S i : s) {
    ++e[x].t[i.first][i.second];
    x = e[x].n[i.first][i.second];
  }
  ++e[x].c;
  for (int i = kL - 2; i >= 0; --i) {
    for (int x = 0; x <= c; ++x) {
      LL v0 = e[x].t[i + 1][0], v1 = e[x].t[i + 1][1];
      e[x].t[i][0] += v0, e[e[x].n[i][0]].t[i][1] += v0;
      e[x].t[i][1] += v1, e[e[x].n[i][1]].t[i][0] += v1;
    }
  }
  for (int x = 0; x <= c; ++x) {
    e[x].c += e[x].t[0][0] + e[x].t[0][1];
  }
  for (int i = t; i >= 1; --i) {
    e[e[d[i]].f].c += e[d[i]].c;
  }
  for (int i = 1; i <= q; ++i) {
    cout << e[p[i]].c << '\n';
  }
  return 0;
}