#include <bits/stdc++.h>
using namespace std;
char s[13];
int p[1 << 12], q[1 << 12], r[1 << 12];
int main() {
  int w, n, m;
  scanf("%d %d %d", &w, &n, &m);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    p[x]++;
  }
  for (int i = 0; i < m; i++) {
    scanf("%s", s);
    reverse(s, s + w);
    for (int j = 0; j < 1 << w; j++) q[j] = p[j];
    for (int j = w - 1; j >= 0; j--) {
      for (int g = 0; g < 1 << w; g++) r[g] = q[g];
      if (s[j] == 'X') {
        for (int g = 0; g < 1 << w; g++) q[g] = r[g];
      } else if (s[j] == 'x') {
        for (int g = 0; g < 1 << w; g++) q[g] = r[g ^ (1 << j)];
      } else if (s[j] == 'A') {
        for (int g = 0; g < 1 << w; g++) {
          if (g & (1 << j)) {
            q[g] = r[g ^ (1 << j)];
          } else {
            q[g] = r[g] + r[g ^ (1 << j)];
          }
        }
      } else if (s[j] == 'a') {
        for (int g = 0; g < 1 << w; g++) {
          if (g & (1 << j)) {
            q[g] = r[g];
          } else {
            q[g] = 0;
          }
        }
      } else if (s[j] == 'O') {
        for (int g = 0; g < 1 << w; g++) {
          if (g & (1 << j)) {
            q[g] = 0;
          } else {
            q[g] = r[g];
          }
        }
      } else if (s[j] == 'o') {
        for (int g = 0; g < 1 << w; g++) {
          if (g & (1 << j)) {
            q[g] = r[g] + r[g ^ (1 << j)];
          } else {
            q[g] = r[g ^ (1 << j)];
          }
        }
      }
    }
    int ans = 0;
    for (int j = 0; j < 1 << w; j++) ans += p[j] * q[j];
    printf("%d\n", ans);
  }
  return 0;
}
