题目描述

JOI 研究所有 $2^L$ 条毒蛇，这些毒蛇编号为 $0, 1, \dots, 2^L-1$。每条毒蛇从头到尾被分成 $L$ 段，每段的颜色为蓝、红中的一种。对于毒蛇 $i$，令 $i=\sum_{k=1}^L c_k\times 2^{L-k}, (0≤c_k≤1)$ 为 $i$ 的二进制展开，若 $c_k=0$，则毒蛇 $i$ 的第 $k$ 段是蓝色的，否则是红色的。

每条毒蛇有一个 $0$ 到 $9$ 的整数表示它的毒性。给出一个长度为 $2^L$ 的字符串，其中字符均在 0 到 9 的范围内，第 $i$ 位字符表示第 $i-1$ 条毒蛇的毒性。

这些毒蛇移动速度非常快，所以他们经常从 JOI 研究所逃跑，因此，研究所附近的住户投诉时常看见从研究所逃出的毒蛇。

研究所整理出了 $Q$ 天来住户的举报清单，第 $d$ 天的收到的举报是一个长度为 $L$ 且仅包含 0, 1, ? 的字符串 $T_d$。

如果 $T_d$ 的第 $j$ 个字符为 0，这意味着逃跑毒蛇的第 $j$ 段是蓝色的；
如果 $T_d$ 的第 $j$ 个字符为 1，这意味着逃跑毒蛇的第 $j$ 段是红色的；
如果 $T_d$ 的第 $j$ 个字符为 ?，这意味着没有人注意到逃跑毒蛇的第 $j$ 段是什么颜色的。

研究所保证投诉均为准确的信息，并且根据这些信息，JOI 研究所每天会将逃跑的毒蛇全部捕获回来，因此会发生同一条毒蛇在不同日子逃跑的情况。

为了估计逃跑的毒蛇的风险，JOI 实验室的执行主任 K 教授想知道所有可能逃跑的毒蛇的毒性之和。你的任务是编写一个程序，给出 $Q$ 天的投诉清单，计算每天可能从实验室逃跑的毒蛇的毒性之和。

注意本题空间限制较小。

输入格式

从标准输入中读取数据。

第一行包括两个整数 $L, Q$，表示毒蛇的颜色段数与收到投诉的天数。

第二行包括一个长度为 $2^L$ 的字符串 $S$，描述毒蛇的毒性。

接下来 $Q$ 行，第 $d+2$ 行有长为 $L$ 的字符串，表示 $T_d$。

输出格式

输出数据到标准输出中。

输出共 $Q$ 行，每行一个整数，表示所有可能逃跑的毒蛇的毒性之和。

样例 1

input

3 5
12345678
000
0??
1?0
?11
???

output

1
10
12
12
36

样例中 $L=3$，共有 $2^3=8$ 条毒蛇，每条毒蛇分成三段，共有 $5$ 天收到投诉。

第一天：逃跑的毒蛇只可能是第 $0$ 条毒蛇，毒性之和为 $1$。 第二天：逃跑的毒蛇只可能是第 $0, 1, 2, 3$ 条毒蛇，毒性之和为 $10$。 第三天：逃跑的毒蛇只可能是第 $4, 6$ 条毒蛇，毒性之和为 $12$。 第四天：逃跑的毒蛇只可能是第 $3, 7$ 条毒蛇，毒性之和为 $12$。 第五天：逃跑的毒蛇只可能是第 $0, 1, 2, 3, 4, 5, 6, 7$ 条毒蛇，毒性之和为 $36$。

样例 2

input

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

output

9
18
38
30
14
15
20
80

数据范围与提示

对于所有输入数据，有 $1≤L≤20, 1≤Q≤10^6$。