AT_joi2018ho_e.毒蛇の脱走 (Snake Escaping)

在 JOI 研究所里饲养着 $2^L$ 条毒蛇，每条毒蛇编号为 $0, 1, \ldots, 2^L - 1$。每条毒蛇的身体从头部开始被分为 $L$ 个部分，每个部分要么是蓝色，要么是红色。对于毒蛇 $i$，将 $i$ 用二进制表示为 $i = \sum_{k=1}^{L} c_k 2^{L-k}$（$0 \leq c_k \leq 1$）时：

• 若 $c_k = 0$，则毒蛇 $i$ 从头部数第 $k$ 个部分为蓝色；
• 若 $c_k = 1$，则毒蛇 $i$ 从头部数第 $k$ 个部分为红色。

每条毒蛇都有一个称为“毒性”的整数值，范围在 $0$ 到 $9$ 之间。给定一个由 0 到 9 组成、长度为 $2^L$ 的字符串 $S$，第 $i$ 个字符（$1 \leq i \leq 2^L$）表示毒蛇 $i-1$ 的毒性。

毒蛇们行动迅速，经常会从 JOI 研究所逃脱。每当有毒蛇逃脱时，周边居民会向研究所投诉。

你将得到 $Q$ 天的投诉信息。第 $d$ 天（$1 \leq d \leq Q$）的投诉信息用一个由 0、1、? 组成、长度为 $L$ 的字符串 $T_d$ 表示：

• $T_d$ 的第 $j$ 个字符（$1 \leq j \leq L$）为 0 时，表示第 $d$ 天逃脱的所有毒蛇从头部数第 $j$ 个部分为蓝色；
• $T_d$ 的第 $j$ 个字符为 1 时，表示第 $d$ 天逃脱的所有毒蛇从头部数第 $j$ 个部分为红色；
• $T_d$ 的第 $j$ 个字符为 ? 时，表示居民未能提供该部分的信息。

所有投诉信息都是准确的。当天逃脱的毒蛇会被研究所工作人员当天抓回，之后不会再次逃脱。

为了评估毒蛇逃脱带来的风险，JOI 研究所的 K 理事长希望知道每天可能逃脱的毒蛇的毒性总和。你的任务是，根据 $Q$ 天的投诉信息，编写程序计算每天可能逃脱的毒蛇的毒性总和。

从标准输入读取以下内容。

• 第 $1$ 行包含两个整数 $L, Q$，用空格分隔，分别表示毒蛇身体部分的数量和投诉天数。
• 第 $2$ 行包含一个长度为 $2^L$ 的字符串 $S$，表示每条毒蛇的毒性。
• 接下来的 $Q$ 行，第 $d$ 行（$1 \leq d \leq Q$）包含一个长度为 $L$ 的字符串 $T_d$，表示第 $d$ 天的投诉信息。

输出 $Q$ 行。第 $d$ 行输出第 $d$ 天可能逃脱的毒蛇的毒性总和。

任务

给定毒蛇毒性字符串 $S$ 和 $Q$ 天的投诉信息，计算每天可能逃脱的毒蛇的毒性总和。

注意内存限制较小。

限制

所有输入数据满足以下条件：

• $1 \leq L \leq 20$。
• $1 \leq Q \leq 1\,000\,000$。
• $S$ 是长度为 $2^L$ 的字符串。
• $S$ 仅包含 0 到 9 的字符。
• $T_d$ 是长度为 $L$ 的字符串（$1 \leq d \leq Q$）。
• $T_d$ 仅包含 0、1、? 字符（$1 \leq d \leq Q$）。

子任务

子任务 1 [5 分]

满足以下条件：

• $L \leq 10$。
• $Q \leq 1\,000$。

子任务 2 [7 分]

• 满足 $L \leq 10$。

子任务 3 [10 分]

• 满足 $L \leq 13$。

子任务 4 [53 分]

• 满足 $Q \leq 50\,000$。

子任务 5 [25 分]

• 无额外限制。

样例解释 1

在此输入样例中，$L = 3$。毒蛇被分为 $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$。

由 ChatGPT 4.1 翻译