CF1033F.Boolean Computer

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, \ldots, 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 \leq i,j \leq n$, such that $w_k(a_i, a_j) = 0$, where $w_k$ is the function computed by the $k$-th "number gate".

Alice 有一台运行在 $w$ 位整数上的计算机。该计算机有 $n$ 个寄存器用于存储数值。当前各寄存器的内容由数组 $a_1, a_2, \ldots, a_n$ 给出。

该计算机使用所谓的“数值门”（number gates）来操作这些数据。每个“数值门”接收两个寄存器作为输入，并计算这两个寄存器中所存数值的某个函数。注意：同一个寄存器可同时作为两个输入。

每个“数值门”由若干“位门”（bit gates）组装而成。共有六种类型的位门：AND（与）、OR（或）、XOR（异或）、NOT AND（与非）、NOT OR（或非）、NOT XOR（异或非），分别用字符 "A"、"O"、"X"、"a"、"o"、"x" 表示。每种位门接收两个比特作为输入，其输出如下表所示（其中 $b_1$、$b_2$ 为输入比特）：

$\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}$

要构造一个“数值门”，需取 $w$ 个位门并将其排成一维阵列。一个“数值门”接收两个 $w$ 位整数 $x_1$ 和 $x_2$ 作为输入。该门将两个整数各自拆分为 $w$ 个比特，并将每个输入的第 $i$ 个比特送入第 $i$ 个位门。随后，将所有位门的输出比特重新组合成一个 $w$ 位输出字。

例如，在一台 4 位计算机上，可能存在一个“数值门”"AXoA"（即：AND、XOR、NOT OR、AND）。对两个输入 $13 = 1101_2$ 和 $10 = 1010_2$，其输出为 $12 = 1100_2$，因为：$1$ AND $1 = 1$，$1$ XOR $0 = 1$，NOT ($0$ OR $1$) = NOT $1 = 0$，最后 $1$ AND $0 = 0$。

现给出 $m$ 个“数值门”的描述。对每个门，你的任务是报告有多少对寄存器使得该“数值门”的输出为 $0$。换言之，求满足 $w_k(a_i, a_j) = 0$ 的有序对 $(i,j)$ 的数量，其中 $1 \leq i,j \leq n$，且 $w_k$ 表示第 $k$ 个“数值门”所计算的函数。

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \lt 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".

第一行包含三个整数：$w$、$n$ 和 $m$（$1 \leq w \leq 12$，$1 \leq n \leq 3\cdot 10^4$，$1 \leq m \leq 5\cdot 10^4$）—— 分别表示字长、变量个数和门电路个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \lt 2^w$）—— 表示存储在寄存器中的各变量的值。

接下来的 $m$ 行中，每行包含一个长度为 $w$ 的字符串 $g_j$，用于描述一个门电路。$g_j$ 的每个字符均为以下之一："A"、"O"、"X"、"a"、"o"、"x"。

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

输出 $m$ 行。第 $i$ 行应包含使得第 $i$ 个逻辑门输出为零的变量有序对的数量。

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 \oplus 10 = 10 \oplus 13 = 12$. The other pairs are $13 \oplus 13 = 11$, $10 \oplus 10 = 8$ and $10 \oplus 6 = 6 \oplus 10 = 4$.

在第一个测试用例中，输入的二进制表示分别为 $1101$、$1010$、$0110$。结果为 $0$ 的数对是 $(13, 6)$、$(6, 13)$ 和 $(6, 6)$。如题目描述中已指出，$13 \oplus 10 = 10 \oplus 13 = 12$。其余数对的结果为：$13 \oplus 13 = 11$、$10 \oplus 10 = 8$，以及 $10 \oplus 6 = 6 \oplus 10 = 4$。