#include <bits/stdc++.h>
using namespace std;
char c[1005];
int lim;
int w;
inline void FWT(int *first, int inv) {
  for (int i = 1, cnt = w - 1; i < lim; i <<= 1, cnt--) {
    if (c[cnt] == 'o' || c[cnt] == 'O') {
      for (int j = 0; j < lim; ++j)
        if (j & i)
          first[j] = inv ? first[j] - first[j ^ i] : first[j] + first[j ^ i];
    }
    if (c[cnt] == 'A' || c[cnt] == 'a') {
      for (int j = 0; j < lim; j += (i << 1))
        for (int k = 0; k < i; ++k)
          first[j + k] = inv ? first[j + k] - first[j + k + i]
                             : first[j + k] + first[j + k + i];
    }
    if (c[cnt] == 'X' || c[cnt] == 'x') {
      for (int j = 0; j < lim; j += (i << 1))
        for (int k = 0; k < i; ++k) {
          int second = first[j + k], z = first[j + k + i];
          first[j + k] = inv ? (second + z) / 2 : second + z;
          first[j + k + i] = inv ? (second - z) / 2 : second - z;
        }
    }
  }
}
int main() {
  int n, m;
  int a[5000];
  memset(a, 0, sizeof(a));
  scanf("%d %d %d", &w, &n, &m);
  lim = 1 << w;
  for (int i = 0; i < n; i++) {
    int first;
    scanf("%d", &first);
    a[first]++;
  }
  int b[5000];
  int k[5000];
  while (m--) {
    scanf("%s", c);
    for (int i = 0; i < lim; i++) k[i] = a[i];
    FWT(k, 0);
    int ans = 0;
    for (int i = 0; i < w; i++) {
      ans <<= 1;
      if (c[i] >= 'a' && c[i] <= 'z') ans++;
    }
    for (int i = 0; i < lim; i++) b[i] = k[i] * k[i];
    FWT(b, 1);
    printf("%d\n", b[ans]);
  }
}
