#include <bits/stdc++.h>
using namespace std;
long long n, m, k, a[1000000], q;
double b[1000000];
char s[1000000];
void fwt(double *a) {
  for (long long i = 0; i < m; i++)
    for (long long j = 0; j < k; j++)
      if (!(j & (1 << i))) {
        if (s[m - i] == 'O' || s[m - i] == 'o') a[j + (1 << i)] += a[j];
        if (s[m - i] == 'A' || s[m - i] == 'a') a[j] += a[j + (1 << i)];
        if (s[m - i] == 'X' || s[m - i] == 'x') {
          a[j] += a[j + (1 << i)];
          a[j + (1 << i)] = a[j] - (a[j + (1 << i)] * 2);
        }
      }
}
void ifwt(double *a) {
  for (long long i = 0; i < m; i++)
    for (long long j = 0; j < k; j++)
      if (!(j & (1 << i))) {
        if (s[m - i] == 'O' || s[m - i] == 'o') a[j + (1 << i)] -= a[j];
        if (s[m - i] == 'A' || s[m - i] == 'a') a[j] -= a[j + (1 << i)];
        if (s[m - i] == 'X' || s[m - i] == 'x') {
          a[j] += a[j + (1 << i)];
          a[j + (1 << i)] = a[j] - (a[j + (1 << i)] * 2);
          a[j] /= 2;
          a[j + (1 << i)] /= 2;
        }
      }
}
signed main() {
  scanf("%lld%lld%lld", &m, &n, &q);
  k = 1 << m;
  for (long long i = 1, x; i <= n; i++) {
    scanf("%lld", &x);
    ++a[x];
  }
  for (long long i = 1; i <= q; i++) {
    scanf("%s", s + 1);
    for (long long i = 0; i < k; i++) b[i] = a[i];
    fwt(b);
    for (long long i = 0; i < k; i++) b[i] *= b[i];
    ifwt(b);
    long long p = 0;
    for (long long i = 0; i < m; i++)
      if (s[m - i] >= 97) p += 1 << i;
    printf("%.0lf\n", b[p]);
  }
  return 0;
}
