#include <bits/stdc++.h>
using namespace std;
int a[4096], u[4096];
char b[14];
int main() {
  int w, n, m;
  scanf("%d%d%d", &w, &n, &m);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    a[x]++;
  }
  int N = 1 << w;
  for (int i = 0; i < N; i++) {
    u[i] = a[i];
  }
  while (m--) {
    scanf("%s", b);
    reverse(b, b + w);
    for (int i = 0; i < w; i++) {
      int l = 1 << i;
      if (b[i] == 'A') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = t;
            a[j + k + l] = s + t;
          }
        }
      } else if (b[i] == 'X') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = s + t;
            a[j + k + l] = s - t;
          }
        }
      } else if (b[i] == 'O') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = s + t;
            a[j + k + l] = s;
          }
        }
      } else if (b[i] == 'a') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = s + t;
            a[j + k + l] = t;
          }
        }
      } else if (b[i] == 'x') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = s - t;
            a[j + k + l] = s + t;
          }
        }
      } else if (b[i] == 'o') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = s;
            a[j + k + l] = s + t;
          }
        }
      }
    }
    for (int i = 0; i < N; i++) {
      a[i] *= a[i];
    }
    for (int i = 0; i < w; i++) {
      int l = 1 << i;
      if (b[i] == 'A') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = -s + t;
            a[j + k + l] = s;
          }
        }
      } else if (b[i] == 'X') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = (s + t) / 2;
            a[j + k + l] = (s - t) / 2;
          }
        }
      } else if (b[i] == 'O') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = t;
            a[j + k + l] = s - t;
          }
        }
      } else if (b[i] == 'a') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = t;
            a[j + k + l] = s - t;
          }
        }
      } else if (b[i] == 'x') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = (-s + t) / 2;
            a[j + k + l] = (-s - t) / 2;
          }
        }
      } else if (b[i] == 'o') {
        for (int j = 0; j < N; j += 2 * l) {
          for (int k = 0; k < l; k++) {
            int s = a[j + k], t = a[j + k + l];
            a[j + k] = -s + t;
            a[j + k + l] = -t;
          }
        }
      }
    }
    printf("%d\n", a[0]);
    for (int i = 0; i < N; i++) {
      a[i] = u[i];
    }
  }
  return 0;
}
