Problem: Alice has a computer that operates on w-bit integers. The computer has n registers for values. The current content of the registers is given as an array a_1, a_2, …, a_n. 

The computer uses so-called "number gates" to manipulate this data. Each "number gate" takes two registers as inputs and calculates a function of the two values stored in those registers. Note that you can use the same register as both inputs.

Each "number gate" is assembled from bit gates. There are six types of bit gates: AND, OR, XOR, NOT AND, NOT OR, and NOT XOR, denoted "A", "O", "X", "a", "o", "x", respectively. Each bit gate takes two bits as input. Its output given the input bits b_1, b_2 is given below:

\begin{matrix} b_1 & b_2 & A & O & X & a & o & x \\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\\ \end{matrix} 

To build a "number gate", one takes w bit gates and assembles them into an array. A "number gate" takes two w-bit integers x_1 and x_2 as input. The "number gate" splits the integers into w bits and feeds the i-th bit of each input to the i-th bit gate. After that, it assembles the resulting bits again to form an output word. 

For instance, for 4-bit computer we might have a "number gate" "AXoA" (AND, XOR, NOT OR, AND). For two inputs, 13 = 1101_2 and 10 = 1010_2, this returns 12 = 1100_2, as 1 and 1 is 1, 1 xor 0 is 1, not (0 or 1) is 0, and finally 1 and 0 is 0. 

You are given a description of m "number gates". For each gate, your goal is to report the number of register pairs for which the "number gate" outputs the number 0. In other words, find the number of ordered pairs (i,j) where 1 ≤ i,j ≤ n, such that w_k(a_i, a_j) = 0, where w_k is the function computed by the k-th "number gate".

Input

The first line contains three integers: w, n, and m~(1 ≤ w ≤ 12, 1 ≤ n ≤ 3⋅ 10^4, 1 ≤ m ≤ 5⋅ 10^4) — the word size, the number of variables, and the number of gates.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i < 2^w) — the value of variables stored in the registers.

Each of the next m lines contains a string g_j~(|g_j| = w) with a description of a single gate. Each character of g_j is one of "A", "O", "X", "a", "o", "x".

Output

Print m lines. The i-th line should contain the number of ordered pairs of variables for which the i-th gate returns zero.

Examples

Input

4 3 1
13 10 6
AXoA


Output

3


Input

1 7 6
0 1 1 0 1 0 0
A
O
X
a
o
x


Output

40
16
25
9
33
24


Input

6 2 4
47 12
AOXaox
AAaaAA
xxxxxx
XXXXXX


Output

2
3
0
2


Input

2 2 2
2 0
xO
Ox


Output

2
0

Note

In the first test case, the inputs in binary are 1101, 1010, 0110. The pairs that return 0 are (13, 6), (6, 13), and (6, 6). As it was already mentioned in the problem statement, 13 ⊕ 10 = 10 ⊕ 13 = 12. The other pairs are 13 ⊕ 13 = 11, 10 ⊕ 10 = 8 and 10 ⊕ 6 = 6 ⊕ 10 = 4. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
struct monostate {
  friend istream& operator>>(istream& is,
                             const __attribute__((unused)) monostate& ms) {
    return is;
  }
  friend ostream& operator<<(ostream& os,
                             const __attribute__((unused)) monostate& ms) {
    return os;
  }
} ms;
template <typename W = monostate>
struct wedge {
  int u, v, i;
  W w;
  wedge<W>(int _u = -1, int _v = -1, int _i = -1) : u(_u), v(_v), i(_i) {}
  int operator[](int loc) const { return u ^ v ^ loc; }
  friend void re(wedge& e) {
    re(e.u, e.v, e.w);
    --e.u, --e.v;
  }
  friend void pr(const wedge& e) { pr(e.u, "<-", e.w, "->", e.v); }
};
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
int have[1 << 12];
int fuzz[531441];
const string ops = "AOXaox";
const int need[6][2] = {{2, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 2}, {1, 0}};
int main() {
  setIO();
  int W, N, M;
  re(W, N, M);
  for (int i = 0; i < (N); i++) {
    int v;
    re(v);
    have[v]++;
  }
  for (int v = 0; v < (1 << W); v++) {
    for (int first = 0; first < (1 << W); first++) {
      int m = 0;
      for (int w = (W)-1; w >= 0; w--) {
        m *= 3;
        if ((first >> w) & 1)
          m += 2;
        else
          m += (v >> w) & 1;
      }
      fuzz[m] += have[v];
    }
  }
  vi p3(W);
  p3[0] = 1;
  for (int w = (1); w < (W); w++) p3[w] = 3 * p3[w - 1];
  for (int m = 0; m < (M); m++) {
    string gate;
    re(gate);
    reverse((gate).begin(), (gate).end());
    vi gop(W);
    for (int i = 0; i < (W); i++) gop[i] = ops.find(gate[i]);
    int ans = 0, first = 0, bad = 0, lv = -1;
    for (int v = 0; v < (1 << W); v++)
      if (have[v]) {
        int d = lv != -1 ? v ^ lv : ((1 << W) - 1);
        while (d) {
          int w = __builtin_ctz(d);
          if (lv != -1) {
            int b = (lv >> w) & 1;
            int n = need[gop[w]][b];
            if (n == -1)
              bad--;
            else
              first -= p3[w] * n;
          }
          {
            int b = (v >> w) & 1;
            int n = need[gop[w]][b];
            if (n == -1)
              bad++;
            else
              first += p3[w] * n;
          }
          d -= 1 << w;
        }
        if (!bad) {
          ans += have[v] * fuzz[first];
        }
        lv = v;
      }
    ps(ans);
  }
  return 0;
}