F. Булевский компьютер
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы есть компьютер, который работает с $$$w$$$-битными целыми числами и имеет $$$n$$$ регистров для чисел. Текущее содержимое регистров задано как массив $$$a_1, a_2, \ldots, a_n$$$.

Компьютер использует так называемые «супер функции», каждая из которых принимает два входных регистра и считает некую функцию, используя те два регистра. Учтите, что вы можете использовать один и тот же регистр как два входных аргумента.

Каждая «супер функция» состоит из логических функций. Существует шесть логических функций: 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$$$ логических операций, разделяет два входных числа $$$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$$$) равно $$$0$$$ и $$$1$$$ AND $$$0$$$ равно $$$0$$$.

Вам дан список всех $$$m$$$ функций. Для каждой функции вам нужно найти количество упорядоченных пар переменных, которые на выходе дадут $$$0$$$. Другими словами, найдите количество упорядоченных пар $$$(i,j)$$$, где $$$1 \leq i,j \leq n$$$, таких что $$$w_k(a_i, a_j) = 0$$$, где $$$w_k$$$ — $$$k$$$-я функция, которую использует «супер функция».

Входные данные

Первая строка содержит три целых числа $$$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 < 2^w)$$$ — значения переменных.

Каждая из следующих $$$m$$$ строк содержит строку $$$g_j~(|g_j| = w)$$$, которая описывает функцию. Строка $$$g_j$$$ содержит только символы «A», «O», «X», «a», «o», «x».

Выходные данные

Выведите $$$m$$$ строк. $$$i$$$-я строка должна содержать количество упорядоченных пар переменных, при которых $$$i$$$-я функция вернет ноль.

Примеры
Входные данные
4 3 1
13 10 6
AXoA
Выходные данные
3
Входные данные
1 7 6
0 1 1 0 1 0 0
A
O
X
a
o
x
Выходные данные
40
16
25
9
33
24
Входные данные
6 2 4
47 12
AOXaox
AAaaAA
xxxxxx
XXXXXX
Выходные данные
2
3
0
2
Входные данные
2 2 2
2 0
xO
Ox
Выходные данные
2
0
Примечание

В первом примере переменные в бинарной записи имеют вид $$$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$$$.