配点: 100 点
在 JOI 学院 2^L 我有两条毒蛇,每条都有一个 它的编号为 0, 1, \ldots, 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 如果是毒蛇 从 i 开始计数 第 k 部分是蓝色的, 第
- c_k = 1 如果是毒蛇 从 i 开始计数 第 k 部分是红色的。
每条毒蛇都称为毒蛇 0 以上 9 以下整数值是固定的。
长度由0,1,2,3,4,5,6,7,8,9 组成 2^L 字符串
给出 S ,其 i 文字目 (1 \leqq i \leqq 2^L) 是一条毒蛇
代表 i - 1 的毒性。
由于毒蛇行动速度快,它们经常从JOI学院逃脱。 JOI研究所收到附近居民的投诉,称他们目睹了毒蛇逃跑。
为了你,Q 给出了天数的投诉信息。
已向d 日目 (1 \leqq d \leqq Q提出投诉)
表示为 0,1,? 组成 L 字符串
给出 T_d ,
- T_d 的 j 文字目 (1 \leqq j \leqq L)是
对于
0,d 从当天逃脱的所有毒蛇的头数开始 代表第 j 部分为蓝色, 表示第 - T_d 的 j 文字目 (1 \leqq j \leqq L)是
对于
1,d 从当天逃脱的所有毒蛇的头数开始 代表第 j 部分为红色, - T_d 的 j 文字目 (1 \leqq j \leqq L)是
对于
?,d 从当天逃脱的毒蛇头开始算 第 j 部分表示周边居民未提供任何信息。
所有投诉均为准确信息。 JOI研究所的工作人员在同一天捕获了逃跑的毒蛇。被捕获的毒蛇有可能第二天再次逃脱。
为了估计毒蛇逃逸的风险,JOI研究所的K主任想知道可能逃逸的毒蛇的总毒性。你的工作是Q 目的是创建一个程序,根据一段时间内的投诉信息,计算出每天可能逃逸的毒蛇的总毒液量。
課題
代表毒蛇毒性的字符串 S 和Q 给定每天的投诉信息,编写一个程序,计算每天可能逃逸的毒蛇的总毒液量。
请注意,内存限制很小。
入力
从标准输入读取以下输入。
- 1 行包含一个整数 L, Q 以空格作为分隔符。这些又代表了毒蛇部位的数量和收到投诉的天数。
- 2 长度是 写入 2^L 字符串 给出 S 。这根绳子代表蛇的毒液。
- 继续 Q 行 d 行目 (1 \leqq d \leqq Q) 的长度 写入 L 字符串 给出 T_d 。这个字符串是 d 代表当天的投诉。
出力
到标准输出 在 Q 行。d 行中,d 打印一个整数,表示第一天可能逃脱的毒蛇的总毒液。
制限
所有输入数据满足以下条件。
- 1 \leqq L \leqq 20.
- 1 \leqq Q \leqq 1\,000\,000.
- S 是长度 它是一个 2^L 字符串。 它由
- 文字列 S 为
0,1,2,3,4,5,6,7,8,9组成。 它是一个字符串 - T_d 是长度 它是一个 L ( 组成为1 \leqq d \leqq Q).
- 文字列 T_d 为
0,1,?(1 \leqq d \leqq Q).
小課題
小課題 1 [5 点]
满足以下条件。
- L \leqq 10.
- Q \leqq 1 000.
小課題 2 [7 点]
- L \leqq 10 很满意。
小課題 3 [10 点]
- L \leqq 13 很满意。
小課題 4 [53 点]
- Q \leqq 50 000 很满意。
小課題 5 [25 点]
- 没有其他限制。
入力例 1
3 5 12345678 000 0?? 1?0 ?11 ???
出力例 1
1 10 12 12 36
在此输入示例中,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 。
入力例 2
4 8 3141592653589793 0101 ?01? ??1? ?0?? 1?00 01?1 ??10 ????
出力例 2
9 18 38 30 14 15 20 80