题目描述

$JOI$ 实验室饲养了 $2^L$ 条毒蛇,每条的编号分别为 $0，1，...，2^L-1$ 。所有的毒蛇都被分为 $L$ 个部分，从头部开始，每个部分都是蓝色或红色。 对于毒蛇 $i$，让$i$ 用 $2$ 位十进制符号表示为$i\ =\ \sum_{k\ =\ 1}^{L}\ c_k\ 2^{L\ -\ k}$ ($0\ \leqq\ c_k\ \leqq\ 1$)

• $c_k = 0$ 那么从毒蛇二号的头部算起，第k个部分是蓝色的。

• $c_k = 1$ 那么从毒蛇二号的头部算起，第k个部分是红色的。

每条毒蛇都有一个定义在0和9之间的整数值，称为它的毒性。

给定一个长度为 $2^L$ 的字符串 $S$，由 1 ~ 9 组成。其中第i个字母（$1\leqq i\leqq 2^L$）代表毒蛇 $i-1$ 的毒性。

由于毒蛇行动迅速，它们经常从 $JOI$ 研究所逃脱，你收到了数次附近居民看到逃脱的毒蛇的举报。

你一共收到了 $Q$ 次举报，在第d天($1\leqq d\leqq Q$)收到了一个长度为 $L$ 的字符串，由 $0,1,?$三种字符组成。

• 如果 $T_d$ ($1\leqq j\leqq L$)的第 $j$ 个字符是 0，这意味着从 $d$ 日逃跑的所有毒蛇的头部算起，第$j$个部分是蓝色的。

• 如果 $T_d$ ($1\leqq j\leqq L$)的第 $j$ 个字符是 1，这意味着从 $d$ 日逃跑的所有毒蛇的头部算起，第$j$个部分是红色的。

• 如果 $T_d$ ($1\leqq j\leqq L$)的第 $j$ 个字符是 1，这意味着从 $d$ 日逃跑的所有毒蛇的头部算起，第$j$个部分是未知的。

所有举报都是准确的。而逃脱的毒蛇会被 $JOI$ 工作人员在当天捕获。被捕获的毒蛇有可能在第二天再次逃跑。

为了估计逃逸的毒蛇的风险，你需要制定一个方案，根据 $Q$ 天内的举报信息，确定每一天可能逃逸的毒蛇的总毒性。

输入格式

第一行包含由空格分隔的整数 $L$ 和 $Q$。表示毒蛇的部位数量和收到举报的天数。

第二行包含长度为 $2^L$ 的字符串 $S$。 表示毒蛇每一个部分的毒性。

最后 $Q$ 行（$1\leqq d\leqq Q$）包含长度为 $L$ 的字符串 $T_d$。 这个字符串代表第 $d$ 天的投诉。

数据范围

对于所有的数据:

• $1 \leqq L \leqq 20$

• $1 \leqq Q \leqq 1 000 000$

对于子问题1 【5pts】:

• $1 \leqq L \leqq 10$

• $1 \leqq Q \leqq 1000$

对于子问题2 【7pts】:

• $1 \leqq L \leqq 10$

对于子问题3 【10pts】:

• $1 \leqq L \leqq 13$

对于子问题4 【53pts】:

• $1 \leqq Q \leqq 50000$

对于子问题5 【25pts】:

• 无其他限制

样例解释

在这个输入例子中，$L=3$，总共有 $2^3=8$ 条毒蛇，分为三部分。 收到了 5 天的投诉。

• 唯一能在第 1 天逃跑的毒蛇是毒蛇 0。 总的毒性是 1。

• 第 2 天可能逃跑的毒蛇是毒蛇 0、1、2 和 3。 总的毒性是 10。

• 第 3 天可能逃跑的毒蛇是毒蛇 4 和 6。 总的毒性为 12。

• 第 4 天可能逃跑的毒蛇是毒蛇 3 和 7 。 总的毒性为 12。

• 第 5 天可能逃跑的毒蛇是毒蛇 0、1、2、3、4、5、6 和 7。 总的毒性是 36。