Custom Bitwise Gate Operation

You are given n non‐negative integers a₁, a₂, …, a_n each in the range \([0,2^w)\). We define a binary operation \(\odot\) on two numbers as follows. The operation is performed bit‐by–bit (from the most significant bit to the least significant bit) according to a given rule string \(s\) of length \(w\). Each character of \(s\) is one of A, O, X, a, o, x and indicates the gate used to combine the two corresponding bits. The interpretation is given by the following truth table (where p and q denote the bits of the two operands):

[ \begin{array}{ccccccc} p & q & 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{array} ]

Specifically, for any two numbers \(x\) and \(y\), if we denote by \(x \odot y\;(s) = z\), then the i^th bit (from the most significant to the least significant) of \(z\) is computed by taking the corresponding bits of \(x\) and \(y\) and applying the gate given by \(s_i\).

You are also given \(q\) queries. In each query you are given a rule string \(s\) (of length \(w\)) and an integer \(z\) (with \(0 \le z < 2^w\)). Your task is to count the number of ordered pairs \((x,y)\) (where indices may be equal) such that

[ a_{x} \odot a_{y} = z. ]

Note: The bits of each number are considered in their \(w\)-bit binary representation (with possible leading zeros) and the operations per bit are independent according to \(s\).

inputFormat

The first line contains three integers \(n\), \(w\) and \(q\) separated by spaces.

The second line contains \(n\) integers \(a₁, a₂, \ldots, a_n\) separated by spaces, each satisfying \(0 \le a_i < 2^w\).

The next \(q\) lines each contain a string \(s\) (of length \(w\)) and an integer \(z\) separated by a space.

outputFormat

For each query, output a single line containing the number of ordered pairs \((x,y)\) such that \(a_x \odot a_y = z\).

sample

3 2 2
0 1 2
AX 1
ox 2

4
2