#include <bits/stdc++.h>
int main(void) {
  int w, n, m;
  while (scanf("%d%d%d", &w, &n, &m) == 3) {
    int wp3 = 1;
    int wp2 = 1;
    for (int i = 0; i < w; i++) {
      wp3 *= 3;
      wp2 *= 2;
    }
    std::vector<int> cnt_simple(wp2, 0);
    std::vector<int> cnt(wp3, 0);
    std::vector<int> conv_to3(wp2, 0);
    for (int i = 0; i < wp2; i++) {
      int nx = 0;
      for (int j = 0; j < w; j++) {
        nx *= 3;
        nx += (i >> (w - j - 1)) & 1;
      }
      conv_to3[i] = nx;
    }
    for (int i = 0; i < n; i++) {
      int x;
      scanf("%d", &x);
      cnt[conv_to3[x]]++;
      cnt_simple[x]++;
    }
    for (int i = 0; i < wp3; i++) {
      for (int j = 0, d = 1; j < w; d *= 3, j++) {
        if ((i / d) % 3 == 2) {
          cnt[i] += cnt[i - d];
          cnt[i] += cnt[i - 2 * d];
          break;
        }
      }
    }
    for (int i = 0; i < m; i++) {
      long long res = 0;
      char s[50];
      scanf("%s", s);
      int A = 0, a = 0, X = 0, x = 0, O = 0, o = 0;
      for (int j = 0; j < w; j++) {
        auto op = s[j];
        int bit = 1 << (w - j - 1);
        switch (op) {
          case 'A':
            A |= bit;
            break;
          case 'X':
            X |= bit;
            break;
          case 'O':
            O |= bit;
            break;
          case 'a':
            a |= bit;
            break;
          case 'x':
            x |= bit;
            break;
          case 'o':
            o |= bit;
            break;
        }
      }
      for (int oldx = 0; oldx < wp2; oldx++) {
        auto new_can = ((oldx & O) | (~oldx & a)) == 0;
        auto new_nx = conv_to3[(((oldx ^ x) & ~A) & ~o) | (~oldx & o)] +
                      (conv_to3[(~oldx & A) + (oldx & o)] * 2);
        long long new_add = 0;
        if (new_can) {
          new_add = (long long)cnt_simple[oldx] * cnt[new_nx];
        }
        res += new_add;
      }
      printf("%lld\n", res);
    }
  }
  return 0;
}
