#include <bits/stdc++.h>
using namespace std;
const int M = 1 << 12;
int fr[M];
int cnt[M * M];
int dup[M];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int w, n, m;
  cin >> w >> n >> m;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    fr[x]++;
  }
  for (int mask = 0; mask < (1 << w); mask++) {
    for (int cmask = 0; cmask < (1 << w); cmask++) {
      int newmask = 0;
      for (int i = 0; i < w; i++) {
        int k = 2 * i;
        if (mask & (1 << i)) k++;
        if (cmask & (1 << i)) newmask |= (1 << k);
      }
      cnt[newmask] += fr[mask];
    }
    for (int i = 0; i < w; i++)
      if (mask & (1 << i))
        dup[mask] |= 1 << (2 * i), dup[mask] |= 1 << (2 * i + 1);
  }
  for (int i = 0; i < m; i++) {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    int set = 0, reset = 0, stay = 0, flip = 0;
    int k = 0;
    for (auto c : s) {
      if (c == 'A')
        stay |= (1 << k);
      else if (c == 'O')
        set |= (1 << k);
      else if (c == 'x')
        stay |= (1 << k);
      else if (c == 'X')
        flip |= (1 << k);
      else if (c == 'o')
        reset |= (1 << k);
      else if (c == 'a')
        flip |= (1 << k);
      k++;
      if (c == 'A')
        reset |= (1 << k);
      else if (c == 'O')
        stay |= (1 << k);
      else if (c == 'x')
        flip |= (1 << k);
      else if (c == 'X')
        stay |= (1 << k);
      else if (c == 'o')
        flip |= (1 << k);
      else if (c == 'a')
        set |= (1 << k);
      k++;
    }
    int ans = 0;
    for (int mask = 0; mask < (1 << w); mask++) {
      int cmask = dup[mask];
      cmask ^= flip;
      cmask |= set;
      cmask &= (~reset);
      ans += fr[mask] * cnt[cmask];
    }
    cout << ans << "\n";
  }
}
