JOI 实验室有 $2^L$ 条毒蛇。这些蛇的编号为 $0, 1, \dots, 2^L - 1$。每条蛇从头到尾被分为 $L$ 个部分。每个部分的颜色要么是蓝色，要么是红色。对于毒蛇 $i$，令 $i = \sum_{k=1}^{L} c_k 2^{L-k}$ ($0 \le c_k \le 1$) 为 $i$ 的二进制表示。那么：
- 如果 $c_k = 0$，则毒蛇 $i$ 从头开始的第 $k$ 个部分的颜色为蓝色；
- 如果 $c_k = 1$，则毒蛇 $i$ 从头开始的第 $k$ 个部分的颜色为红色。
每条毒蛇都有一个 $0$ 到 $9$ 之间的整数，称为毒性。给定一个长度为 $2^L$ 的字符串 $S$，由 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ 组成。第 $i$ 个字符（$1 \le i \le 2^L$）表示编号为 $i-1$ 的毒蛇的毒性。
由于毒蛇行动敏捷，它们经常从 JOI 实验室逃跑。住在实验室附近的居民看到了逃跑的毒蛇，并向 JOI 实验室投诉。
你将获得 $Q$ 天的投诉列表。第 $d$ 天（$1 \le d \le Q$）的投诉是一个长度为 $L$ 的字符串 $T_d$，由 $0, 1, ?$ 组成。
- 如果 $T_d$ 的第 $j$ 个字符（$1 \le j \le L$）为 $0$，这意味着在第 $d$ 天从实验室逃跑的每条毒蛇的第 $j$ 个部分都是蓝色的；
- 如果 $T_d$ 的第 $j$ 个字符（$1 \le j \le L$）为 $1$，这意味着在第 $d$ 天从实验室逃跑的每条毒蛇的第 $j$ 个部分都是红色的；
- 如果 $T_d$ 的第 $j$ 个字符（$1 \le j \le L$）为 $?$，这意味着关于第 $d$ 天从实验室逃跑的毒蛇的第 $j$ 个部分，居民没有提供任何信息。
所有的投诉都是准确的信息。所有从实验室逃跑的毒蛇都在同一天被 JOI 实验室的工作人员抓回。同一条蛇可能会在不同的日子逃跑。
为了评估毒蛇逃跑的风险，JOI 实验室执行主任 K 教授想要知道可能从实验室逃跑的蛇的毒性之和。你的任务是编写一个程序，根据给定的 $Q$ 天投诉列表，计算每天可能从实验室逃跑的蛇的毒性之和。
注意本题内存限制较小。
输入格式
从标准输入读取以下数据：
- 第一行包含两个空格分隔的整数 $L, Q$。它们分别是每条毒蛇的身体部分数量和投诉的天数。
- 第二行包含一个长度为 $2^L$ 的字符串 $S$。它描述了毒蛇的毒性。
- 接下来的 $Q$ 行中的第 $d$ 行（$1 \le d \le Q$）包含一个长度为 $L$ 的字符串 $T_d$。它是第 $d$ 天的投诉。
输出格式
向标准输出写入 $Q$ 行。第 $d$ 行应包含一个整数，表示第 $d$ 天可能从实验室逃跑的蛇的毒性之和。
数据范围
所有输入数据满足以下条件：
- $1 \le L \le 20$。
- $1 \le Q \le 1\,000\,000$。
- $S$ 是一个长度为 $2^L$ 的字符串。
- 字符串 $S$ 由 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ 组成。
- $T_d$ 是一个长度为 $L$ 的字符串（$1 \le d \le Q$）。
- 字符串 $T_d$ 由 $0, 1, ?$ 组成（$1 \le d \le Q$）。
子任务
子任务 1 [5 分]
满足以下条件： $L \le 10$。 $Q \le 1\,000$。
子任务 2 [7 分]
- $L \le 10$。
子任务 3 [10 分]
- $L \le 13$。
子任务 4 [53 分]
- $Q \le 50\,000$。
子任务 5 [25 分]
- 没有额外限制。
样例
样例输入 1
3 5 12345678 000 0?? 1?0 ?11 ???
样例输出 1
1 10 12 12 36
说明
在该样例输入中，$L = 3$。共有 $2^3 = 8$ 条毒蛇。每条蛇被分为 3 个部分。投诉给出了 5 天的情况。
- 第一天，可能从实验室逃跑的毒蛇只有毒蛇 0。毒性之和为 1。
- 第二天，可能从实验室逃跑的毒蛇是毒蛇 0, 1, 2, 3。毒性之和为 10。
- 第三天，可能从实验室逃跑的毒蛇是毒蛇 4, 6。毒性之和为 12。
- 第四天，可能从实验室逃跑的毒蛇是毒蛇 3, 7。毒性之和为 12。
- 第五天，可能从实验室逃跑的毒蛇是毒蛇 0, 1, 2, 3, 4, 5, 6, 7。毒性之和为 36。
样例输入 2
4 8 3141592653589793 0101 ?01? ??1? ?0?? 1?00 01?1 ??10 ????
样例输出 2
9 18 38 30 14 15 20 80