#include <bits/stdc++.h>
using namespace std;
const int SZ = 600100;
int dp[SZ], st[20], w, n, m, a[30100], kol[5100];
inline int getBit(int mask, int pos) { return ((mask / st[pos]) % 3); }
string s;
int ans = 0;
void rec(int j, int mask, int needMask) {
  if (j == w) {
    int curkol = dp[needMask];
    ans += kol[mask] * curkol;
    return;
  }
  bool bb = 1;
  int needMaskPrev = needMask;
  if (s[j] == 'A') {
    if (mask & (1 << j))
      needMask += 0;
    else
      needMask += st[j] * 2;
  } else if (s[j] == 'O') {
    if (mask & (1 << j)) {
      bb = 0;
    }
  } else if (s[j] == 'X') {
    if (mask & (1 << j)) {
      needMask += st[j];
    }
  } else if (s[j] == 'a') {
    if (mask & (1 << j)) {
      needMask += st[j];
    } else {
      bb = 0;
    }
  } else if (s[j] == 'o') {
    if (mask & (1 << j))
      needMask += st[j] * 2;
    else
      needMask += st[j];
  } else {
    if (mask & (1 << j))
      needMask += 0;
    else
      needMask += st[j];
  }
  if (bb == 1) rec(j + 1, mask, needMask);
  bb = 1;
  needMask = needMaskPrev;
  mask += (1 << j);
  if (s[j] == 'A') {
    if (mask & (1 << j))
      needMask += 0;
    else
      needMask += st[j] * 2;
  } else if (s[j] == 'O') {
    if (mask & (1 << j)) {
      bb = 0;
    }
  } else if (s[j] == 'X') {
    if (mask & (1 << j)) {
      needMask += st[j];
    }
  } else if (s[j] == 'a') {
    if (mask & (1 << j)) {
      needMask += st[j];
    } else {
      bb = 0;
    }
  } else if (s[j] == 'o') {
    if (mask & (1 << j))
      needMask += st[j] * 2;
    else
      needMask += st[j];
  } else {
    if (mask & (1 << j))
      needMask += 0;
    else
      needMask += st[j];
  }
  if (bb == 1) rec(j + 1, mask, needMask);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  st[0] = 1;
  int mxStep = 1;
  for (int i = 1; i <= 12; i++) st[i] = st[i - 1] * 3;
  cin >> w >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ++kol[a[i]];
    int mask = 0;
    for (int j = 0; j < w; j++)
      if (a[i] & (1 << j)) mask += st[j];
    ++dp[mask];
  }
  for (int i = 0; i < w; i++) mxStep *= 3;
  for (int i = 0; i < w; i++) {
    for (int mask = 0; mask < mxStep; mask++) {
      int bt = (mask / st[i]) % 3;
      if (bt != 2) {
        dp[mask - bt * st[i] + 2 * st[i]] += dp[mask];
      }
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> s;
    reverse(s.begin(), s.end());
    ans = 0;
    rec(0, 0, 0);
    cout << ans << "\n";
  }
}
