#include <bits/stdc++.h>
using namespace std;
const int W = 12;
const int N = 5e4 + 5;
int w, n, m;
int a[1 << W], dp[1 << (W + W)];
char s[12];
int main() {
  scanf("%d %d %d", &w, &n, &m);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    int nx = 0;
    for (int j = 0; j < w; j++) {
      nx <<= 1;
      if (x & (1 << j)) nx |= 1;
    }
    a[nx]++;
    dp[nx]++;
  }
  for (int i = 0; i < w; i++) {
    int close = ((1 << (w + w)) - 1) ^ (1 << i);
    int open = 1 << (w + i);
    for (int mask = 0; mask < (1 << (w + w)); mask++) {
      if (!(mask & open)) {
        dp[(mask & close) ^ open] += dp[mask];
      }
    }
  }
  while (m--) {
    scanf("%s", s);
    int not_case_w = 0;
    int fail_case = 0;
    int and_case = 0;
    int not_fail_case = 0;
    int and_case_w = 0;
    ;
    int not_case = 0;
    for (int j = 0; j < w; j++) {
      if (s[j] == 'A') {
        not_case_w |= 1 << j;
      } else if (s[j] == 'O') {
        fail_case |= 1 << j;
      } else if (s[j] == 'X') {
        and_case |= 1 << j;
      } else if (s[j] == 'a') {
        and_case |= 1 << j;
        not_fail_case |= 1 << j;
      } else if (s[j] == 'o') {
        and_case_w |= 1 << j;
        not_case |= 1 << j;
      } else if (s[j] == 'x') {
        not_case |= 1 << j;
      }
    }
    int ans = 0;
    for (int i = 0; i < (1 << w); i++) {
      int j = ((1 << w) - 1) ^ i;
      if ((fail_case & i) or (not_fail_case & j)) continue;
      int need = 0;
      need |= (i & and_case);
      need |= (i & and_case_w) << w;
      need |= (j & not_case);
      need |= (j & not_case_w) << w;
      ans += dp[need] * a[i];
    }
    printf("%d\n", ans);
  }
  return 0;
}
