#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int arr = 2e5 + 10;
const int ar = 2e3 + 10;
const long double pi = acos(-1);
const long double eps = 1e-10;
const long long md = 1e9 + 7;
int cnt[(1ll << 12)][(1ll << 12)];
pair<pair<int, int>, bool> cnt1_w[4][6 * 6 * 6 * 6][(1ll << 4)];
int type[arr];
int a[arr];
int w, n, q;
pair<pair<int, int>, bool> get_kek(int p, int m, int mm) {
  pair<pair<int, int>, bool> res = make_pair(make_pair(0, 0), 0);
  for (int i = 0; i < p; i++) {
    int cur_type = m % 6;
    m /= 6;
    if (cur_type == 0) {
      if (mm & (1ll << i)) {
      } else {
        res.first.first ^= (1ll << i);
      }
    }
    if (cur_type == 1) {
      if (mm & (1ll << i)) {
        res.second = 1;
      } else {
      }
    }
    if (cur_type == 2) {
      if (mm & (1ll << i)) {
        res.first.second ^= (1ll << i);
      } else {
      }
    }
    if (cur_type == 3) {
      if (mm & (1ll << i)) {
        res.first.second ^= (1ll << i);
      } else {
        res.second = 1;
      }
    }
    if (cur_type == 4) {
      if (mm & (1ll << i)) {
        res.first.first ^= (1ll << i);
      } else {
        res.first.second ^= (1ll << i);
      }
    }
    if (cur_type == 5) {
      if (mm & (1ll << i)) {
      } else {
        res.first.second ^= (1ll << i);
      }
    }
  }
  return res;
}
int pw(int a, int n) {
  int res = 1;
  while (n--) {
    res *= a;
  }
  return res;
}
void precalc() {
  for (int p = 1; p <= 4; p++) {
    for (int m = 0; m < pw(6, p); m++) {
      for (int mm = 0; mm < (1ll << p); mm++) {
        cnt1_w[p - 1][m][mm] = get_kek(p, m, mm);
      }
    }
  }
}
inline bool podmask(int a, int b) { return ((a & b) == a); }
int cnt1[arr];
int main() {
  precalc();
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> w >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    for (int j = 0; j < (1ll << w); j++) {
      cnt[j][a[i] ^ j]++;
    }
    cnt1[a[i]]++;
  }
  for (int j = 0; j < (1ll << w); j++) {
    for (int i = 0; i < w; i++) {
      for (int k = 0; k < (1ll << w); k++) {
        if (k & (1ll << i)) {
          cnt[j][k] += cnt[j][k ^ (1ll << i)];
        }
      }
    }
  }
  pair<pair<int, int>, bool> lolik;
  pair<pair<int, int>, bool> lolik1;
  pair<pair<int, int>, bool> lolik2;
  pair<pair<int, int>, bool> lolik3;
  if (w <= 8) {
    for (int i = 0; i < q; i++) {
      string s;
      cin >> s;
      int ans = 0;
      for (int j = 0; j < w; j++) {
        if (s[j] == 'A') {
          type[j] = 0;
        }
        if (s[j] == 'O') {
          type[j] = 1;
        }
        if (s[j] == 'X') {
          type[j] = 2;
        }
        if (s[j] == 'a') {
          type[j] = 0 + 3;
        }
        if (s[j] == 'o') {
          type[j] = 1 + 3;
        }
        if (s[j] == 'x') {
          type[j] = 2 + 3;
        }
      }
      int mask_req = 0;
      int mask_req_first_4 = 0;
      int mask_req_after_4_before_8 = 0;
      int mask_req_after_8_before_12 = 0;
      if (w <= 4) {
        for (int j = 0; j < w; j++) {
          mask_req *= 6;
          mask_req += type[j];
        }
      } else if (w <= 8) {
        for (int j = w - 4; j < w; j++) {
          mask_req_first_4 *= 6;
          mask_req_first_4 += type[j];
        }
        for (int j = 0; j < w - 4; j++) {
          mask_req_after_4_before_8 *= 6;
          mask_req_after_4_before_8 += type[j];
        }
      } else {
        for (int j = w - 4; j < w; j++) {
          mask_req_first_4 *= 6;
          mask_req_first_4 += type[j];
        }
        for (int j = w - 8; j < w - 4; j++) {
          mask_req_after_4_before_8 *= 6;
          mask_req_after_4_before_8 += type[j];
        }
        for (int j = 0; j < w - 8; j++) {
          mask_req_after_8_before_12 *= 6;
          mask_req_after_8_before_12 += type[j];
        }
      }
      for (int j = 0; j < (1ll << w); j++) {
        if (w <= 4) {
          lolik = cnt1_w[w - 1][mask_req][j];
        } else if (w <= 8) {
          lolik1 = cnt1_w[4 - 1][mask_req_first_4][j & ((1ll << 4) - 1)];
          lolik2 = cnt1_w[w - 4 - 1][mask_req_after_4_before_8][j >> 4];
          lolik.first.first = lolik1.first.first + ((lolik2.first.first) << 4);
          lolik.first.second =
              lolik1.first.second + ((lolik2.first.second) << 4);
          lolik.second = lolik1.second | lolik2.second;
        } else {
          lolik1 = cnt1_w[4 - 1][mask_req_first_4][j & ((1ll << 4) - 1)];
          lolik2 = cnt1_w[4 - 1][mask_req_after_4_before_8]
                         [(j >> 4) & ((1ll << 4) - 1)];
          lolik3 = cnt1_w[w - 8 - 1][mask_req_after_8_before_12][j >> 8];
          lolik.first.first = lolik1.first.first + ((lolik2.first.first) << 4) +
                              ((lolik3.first.first) << 8);
          lolik.first.second = lolik1.first.second +
                               ((lolik2.first.second) << 4) +
                               ((lolik3.first.second) << 8);
          lolik.second = lolik1.second | lolik2.second | lolik3.second;
        }
        if (!lolik.second) {
          ans += (cnt[lolik.first.second][lolik.first.first] * cnt1[j]);
        }
      }
      cout << ans << "\n";
    }
  } else {
    map<string, int> answer;
    for (int i = 0; i < q; i++) {
      string s;
      cin >> s;
      int ans = 0;
      for (int j = 0; j < w; j++) {
        if (s[j] == 'A') {
          type[j] = 0;
        }
        if (s[j] == 'O') {
          type[j] = 1;
        }
        if (s[j] == 'X') {
          type[j] = 2;
        }
        if (s[j] == 'a') {
          type[j] = 0 + 3;
        }
        if (s[j] == 'o') {
          type[j] = 1 + 3;
        }
        if (s[j] == 'x') {
          type[j] = 2 + 3;
        }
      }
      int mask_req_first_4 = 0;
      int mask_req_after_4_before_8 = 0;
      int mask_req_after_8_before_12 = 0;
      for (int j = w - 4; j < w; j++) {
        mask_req_first_4 *= 6;
        mask_req_first_4 += type[j];
      }
      for (int j = w - 8; j < w - 4; j++) {
        mask_req_after_4_before_8 *= 6;
        mask_req_after_4_before_8 += type[j];
      }
      for (int j = 0; j < w - 8; j++) {
        mask_req_after_8_before_12 *= 6;
        mask_req_after_8_before_12 += type[j];
      }
      if (answer.count(s)) {
        cout << answer[s] << "\n";
        continue;
      }
      for (int j = 0; j < (1ll << w); j++) {
        lolik1 = cnt1_w[4 - 1][mask_req_first_4][j & ((1ll << 4) - 1)];
        lolik2 = cnt1_w[4 - 1][mask_req_after_4_before_8]
                       [(j >> 4) & ((1ll << 4) - 1)];
        lolik3 = cnt1_w[w - 8 - 1][mask_req_after_8_before_12][j >> 8];
        lolik.first.first = lolik1.first.first + ((lolik2.first.first) << 4) +
                            ((lolik3.first.first) << 8);
        lolik.first.second = lolik1.first.second +
                             ((lolik2.first.second) << 4) +
                             ((lolik3.first.second) << 8);
        lolik.second = lolik1.second | lolik2.second | lolik3.second;
        if (!lolik.second) {
          ans += (cnt[lolik.first.second][lolik.first.first] * cnt1[j]);
        }
      }
      answer[s] = ans;
      cout << ans << "\n";
    }
  }
}
