#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 12;
int frc[N + 1];
int dp[N + 1][N + 1];
int w, tot1;
int v[N + 1], cnt;
void calc_dp() {
  for (int mask0 = 0; mask0 < (1 << w); mask0++) {
    int max1 = tot1 - mask0;
    cnt = 0;
    for (int i = max1; i; i = (i - 1) & max1) {
      v[++cnt] = i;
    }
    while (cnt) {
      int val = v[cnt--];
      for (int i = (val - 1) & val;; i = (i - 1) & val) {
        dp[mask0][i] += dp[mask0][val];
        if (i == 0) break;
      }
    }
  }
}
char poz[300];
int mask[6];
void get_mask(string gate) {
  memset(mask, 0, sizeof mask);
  for (int i = 0; i < gate.size(); i++) mask[poz[gate[i]]] |= (1 << i);
}
inline int get_nr(int x) {
  int posibil = 0;
  int mask0 = 0, mask1 = 0;
  mask0 |= x & mask[poz['A']];
  mask0 |= mask[poz['O']];
  posibil |= x & mask[poz['O']];
  mask0 |= (~x) & mask[poz['X']];
  mask1 |= x & mask[poz['X']];
  mask1 |= mask[poz['a']];
  posibil |= (~x) & mask[poz['a']];
  mask1 |= (~x) & mask[poz['o']];
  mask1 |= (~x) & mask[poz['x']];
  mask0 |= x & mask[poz['x']];
  if (posibil) return 0;
  return dp[mask0][mask1];
}
int main() {
  poz['A'] = 0;
  poz['O'] = 1;
  poz['X'] = 2;
  poz['a'] = 3;
  poz['o'] = 4;
  poz['x'] = 5;
  int n, m;
  scanf("%d%d%d", &w, &n, &m);
  tot1 = (1 << w) - 1;
  while (n--) {
    int x;
    scanf("%d", &x);
    frc[x]++;
    int mask1 = x, mask0 = (~x) & tot1;
    for (int i = mask0;; i = (i - 1) & mask0) {
      dp[i][mask1]++;
      if (i == 0) break;
    }
  }
  calc_dp();
  while (m--) {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    get_mask(s);
    long long ans = 0;
    for (int i = 0; i <= tot1; i++) ans += get_nr(i) * frc[i];
    cout << ans << '\n';
  }
  return 0;
}
