#include <bits/stdc++.h>
using namespace std;
const string GATES = "AOXaox";
int W, N, M;
vector<uint16_t> freq;
vector<uint16_t> quick_count;
int needed(char bit_gate, int bit) {
  switch (bit_gate) {
    case 'A':
      return bit == 0 ? 2 : 0;
    case 'O':
      return bit == 0 ? 0 : 3;
    case 'X':
      return bit;
    case 'a':
      return bit == 0 ? 3 : 1;
    case 'o':
      return bit == 0 ? 1 : 2;
    case 'x':
      return bit ^ 1;
  }
  assert(false);
}
int8_t gates[12];
int8_t gate_needed[6][2];
int solve(string gate_str) {
  assert((int)gate_str.size() == W);
  reverse(gate_str.begin(), gate_str.end());
  for (int i = 0; i < W; i++) {
    gates[i] = GATES.find(gate_str[i]);
    assert(0 <= gates[i] && gates[i] < 6);
  }
  int extended = 0, threes = 0, answer = 0;
  for (int mask = 0; mask < 1 << W; mask++) {
    for (int i = 0; i < W; i++) {
      if ((extended >> 2 * i) % 4 == 3) threes--;
      extended ^= extended & 3 << 2 * i;
      int need = gate_needed[gates[i]][mask & 1 << i ? 1 : 0];
      if (need == 3) threes++;
      extended ^= need << 2 * i;
      if (mask & 1 << i) break;
    }
    if (threes == 0) answer += freq[mask] * quick_count[extended];
  }
  return answer;
}
int main() {
  scanf("%d %d %d", &W, &N, &M);
  freq.resize(1 << W);
  for (int i = 0; i < N; i++) {
    int v;
    scanf("%d", &v);
    freq[v]++;
  }
  quick_count.resize(1 << 2 * W);
  for (int a = 0; a < 1 << W; a++) {
    int expanded = 0;
    for (int i = 0; i < W; i++)
      if (a & 1 << i) expanded += 1 << 2 * i;
    quick_count[expanded] = freq[a];
  }
  int a = 0;
  while (a < 1 << 2 * W) {
    for (int i = 0; i < W; i++)
      if ((a >> 2 * i) % 4 == 2) {
        quick_count[a] =
            quick_count[a - (2 << 2 * i)] + quick_count[a - (1 << 2 * i)];
        break;
      }
    int index = W;
    for (int i = 0; i < W; i++)
      if ((a >> 2 * i) % 4 == 2) {
        a ^= a & 3 << 2 * i;
      } else {
        index = i;
        break;
      }
    a += 1 << 2 * index;
  }
  for (int type = 0; type < (int)GATES.size(); type++) {
    gate_needed[type][0] = needed(GATES[type], 0);
    gate_needed[type][1] = needed(GATES[type], 1);
  }
  for (int i = 0; i < M; i++) {
    char gate[100];
    scanf("%s", gate);
    printf("%d\n", solve(gate));
  }
}
