#include <bits/stdc++.h>
#pragma GCC optimize "-O3"
using namespace std;
const int N = 1 << 20;
const double pi = acos(-1);
namespace polynomial {
int rev(int mask, int nbit) {
  for (int i = 0, j = nbit - 1; i < j; ++i, --j)
    if ((mask >> i & 1) != (mask >> j & 1)) {
      mask ^= (1 << i);
      mask ^= (1 << j);
    }
  return mask;
}
void FFT(int n, vector<complex<double> >& a, bool inv) {
  if (n == 1) return;
  for (int i = 0; i < n; ++i) {
    int j = rev(i, log2(n));
    if (i < j) swap(a[i], a[j]);
  }
  for (int k = 1; k < n; k <<= 1) {
    double alp = pi / k;
    if (inv) alp = -alp;
    complex<double> u(cos(alp), sin(alp));
    for (int i = 0; i < n; i += 2 * k) {
      complex<double> W(1);
      for (int j = 0; j < k; ++j) {
        complex<double> x = a[i + j], y = a[i + j + k] * W;
        a[i + j] = x + y;
        a[i + j + k] = x - y;
        W *= u;
      }
    }
  }
  if (inv)
    for (int i = 0; i < n; ++i) a[i] /= n;
}
};  // namespace polynomial
using polynomial::FFT;
vector<complex<double> > p(N);
pair<int, int> a[12];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int w, n, m;
  cin >> w >> n >> m;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    int y = 0;
    for (int j = w - 1; ~j; --j) {
      y *= 3;
      y += (x >> j & 1);
    }
    p[y] += 1;
  }
  FFT(N, p, 0);
  for (int i = 0; i < N; ++i) p[i] = p[i] * p[i];
  FFT(N, p, 1);
  string s;
  while (m--) {
    for (int i = 0; i < w; ++i) {
      char c;
      cin >> c;
      if (c == 'A') a[i] = pair<int, int>(0, 1);
      if (c == 'O') a[i] = pair<int, int>(0, 0);
      if (c == 'X') a[i] = pair<int, int>(0, 2);
      if (c == 'a') a[i] = pair<int, int>(2, 0);
      if (c == 'o') a[i] = pair<int, int>(1, 2);
      if (c == 'x') a[i] = pair<int, int>(1, 0);
    }
    long long ans = 0;
    function<void(int, int)> bt = [&](int P, int x) {
      if (P == w) {
        ans += round(p[x].real());
        return;
      }
      bt(P + 1, x * 3 + a[P].first);
      if (a[P].second) bt(P + 1, x * 3 + a[P].second);
    };
    bt(0, 0);
    cout << ans << "\n";
  }
}
