题目描述

定义一种二元位运算为 $\odot$ ，运算数均在区间 $[0,2^w)$ 内，他使用数字门进行运算，运算法则由一个长度为 $w$ 的字符串构成，设为 $s$，$s$ 仅包含 $\texttt{A,O,X,a,o,x}$，分别表示 与，或，异或，与非，或非，同或，表示每一位的运算法则。以下是这些位运算的真值表，$p,q$ 为参与运算的两个数：

$$\begin{matrix}\texttt{p\ q\ A\ O\ X\ a\ o\ x}\\\texttt{0\ 0\ 0\ 0\ 0\ 1\ 1\ 1}\\\texttt{0\ 1\ 0\ 1\ 1\ 1\ 0\ 0}\\\texttt{1\ 0\ 0\ 1\ 1\ 1\ 0\ 0}\\\texttt{1\ 1\ 1\ 1\ 0\ 0\ 0\ 1}\end{matrix} $$

具体地，$x\odot y \ (s) =z$ 的运算方式如下：

• $z$ 的二进制的从高到低第 $i$ 位的结果是 $x$ 和 $y$ 的第 $i$ 位通过 $s_i$ 对应的运算得到的。

给定 $n$ 个 $[0,2^w)$ 中的数 $a_1,a_2,\cdots ,a_n$ 和 $q$ 组询问，每次询问给定门运算的运算法则 $s$，询问有多少对有序对 $(x,y)$ 满足 $a_x \odot a_y = z$（注意 $x$ 可以等于 $y$）。

输入格式

第一行四个正整数 $T,w,n,q$，分别表示测试点编号，运算法则长度，$a$ 序列长度和询问数量。

第二行 $n$ 个整数，表示 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行一个字符串 $s$ 和一个非负整数 $z$。

输出格式

对于每个询问，输出一个非负整数，表示符合要求的有序对 $(x,y)$ 数量。

0 3 4 3
3 3 7 0
XAo 0
XAX 5
XaA 2

4
2
5

0 5 10 5
9 14 29 16 18 14 20 6 23 16
axaxa 0
aaOOa 0
OaOxO 0
OaOOa 0
axaaO 0

2
0
0
1
0

提示

测试点编号	$w\leq$	$n\leq$	$q\leq$	特殊性质
$1\sim 3$	$16$	$100$	$10$	无
$4\sim 5$	$8$	$10^5$
$6\sim9$	$10$		$10^4$
$10\sim 12$	$11$		$3\times10^4$
$13\sim14$	$12$		$5\times10^4$
$15\sim16$	$13$		$7\times10^4$
$17\sim19$	$14$		$10^5$
$20\sim21$	$16$			$s_i$ 仅包含 $\texttt{O,a,x}$，$z_i=0$
$22\sim25$				无

对于 $100\%$ 的数据：$1\leq w\leq 16$，$1\leq n\leq10^5$，$1\leq q\leq 10^5$，$0\leq z_i,a_i<2^w$，$|s_i|=w$ 且 $s_i$ 仅包含 $\texttt{A,O,X,a,o,x}$。