#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000020;
const int maxx = 1 << 12;
int w, n, m;
int N = 1, nex[maxn][3];
int num[maxx];
long long V[maxn];
int go(int p, int n, int &x, int &y, long long &val) {
  if (p == 0) p = ++N;
  if (n == -1) {
    V[p] += val;
    return p;
  }
  int h = 0;
  if (!(x & (1 << n)) && !(y & (1 << n)))
    h = 0;
  else if ((x & (1 << n)) && (y & (1 << n)))
    h = 2;
  else
    h = 1;
  nex[p][h] = go(nex[p][h], n - 1, x, y, val);
  return p;
}
string s;
long long f(int p, int n) {
  if (p == 0) return 0;
  if (n == s.size()) return V[p];
  char ch = s[n];
  if (ch == 'A') return f(nex[p][0], n + 1) + f(nex[p][1], n + 1);
  if (ch == 'a') return f(nex[p][2], n + 1);
  if (ch == 'o') return f(nex[p][1], n + 1) + f(nex[p][2], n + 1);
  if (ch == 'O') return f(nex[p][0], n + 1);
  if (ch == 'X') return f(nex[p][0], n + 1) + f(nex[p][2], n + 1);
  if (ch == 'x') return f(nex[p][1], n + 1);
  assert(0);
}
int main() {
  scanf("%d %d %d", &w, &n, &m);
  for (int i = 1, j; i <= n; i++) {
    scanf("%d", &j);
    num[j]++;
  }
  int mask = 1 << w;
  for (int i = 0; i < mask; i++)
    for (int j = 0; j < mask; j++) {
      long long val = (long long)num[i] * num[j];
      if (val) {
        go(1, w - 1, i, j, val);
      }
    }
  while (m--) {
    cin >> s;
    assert(s.size() == w);
    cout << f(1, 0) << endl;
  }
  return 0;
}
