#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10, M = 5e4 + 10, W = 12;
const int C = 300;
int ctr[1 << W];
int dp[1 << (2 * W)];
int mp[C][2];
bool eval(char gate, bool v1, bool v2);
void print(int mask, int w);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int w, n, m;
  cin >> w >> n >> m;
  for (int i = 1; i <= n; ++i) {
    int val;
    cin >> val;
    ++ctr[val];
  }
  int p3 = 1;
  for (int i = 0; i < w; ++i, p3 *= 3)
    ;
  for (int k = 0; k < p3; ++k) {
    int i = 0;
    for (int j = 0, shift = 1; j < 2 * w; j += 2, shift *= 3) {
      int temp = ((k / shift) % 3) + 1;
      i |= (temp << j);
    }
    bool done = false;
    int mask = 0;
    for (int j = 0; j < 2 * w; j += 2) {
      int temp = (i >> j) & 3;
      if (!temp) {
        done = true;
        break;
      } else if (temp == 3) {
        dp[i] = dp[i ^ (1 << j)] + dp[i ^ (1 << (j + 1))];
        done = true;
        break;
      } else if (temp == 2) {
        mask |= (1 << (j / 2));
      }
    }
    if (!done) {
      dp[i] = ctr[mask];
    }
  }
  vector<char> gates = {'A', 'O', 'X', 'a', 'o', 'x'};
  for (auto &c : gates) {
    for (int d1 = 0; d1 < 2; ++d1) {
      for (int d2 = 0; d2 < 2; ++d2) {
        if (!eval(c, d1, d2)) {
          mp[c][d1] |= (1 << d2);
        }
      }
    }
  }
  int total = (1 << w);
  for (int i = 0; i < m; ++i) {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    int mask = 0;
    long long ans = 0;
    for (int b = 0; b < w; ++b) {
      mask |= (mp[s[b]][0] << (2 * b));
    }
    for (int val = 0; val < total; ++val) {
      if (val > 0) {
        for (int b = 0; b < w; ++b) {
          if (((val >> b) & 1) == (((val - 1) >> b) & 1)) {
            break;
          }
          mask &= ((1 << (2 * w)) - 1) ^ (3 << (2 * b));
          mask |= (mp[s[b]][(val >> b) & 1] << (2 * b));
        }
      }
      ans += ctr[val] * dp[mask];
    }
    cout << ans << '\n';
  }
}
bool eval(char gate, bool v1, bool v2) {
  switch (gate) {
    case 'A':
      return v1 and v2;
    case 'a':
      return !(v1 and v2);
    case 'O':
      return v1 or v2;
    case 'o':
      return !(v1 or v2);
    case 'X':
      return v1 xor v2;
    case 'x':
      return !(v1 xor v2);
  }
}
void print(int mask, int w) {
  for (int i = 0; i < (2 * w); i += 2) {
    int temp = (mask >> i) & 3;
    cout << temp;
  }
  cout << ' ';
}
