Problem Description

JOI Laboratory keeps $2^L$ poisonous snakes, each labeled with numbers $0, 1, \ldots, 2^L - 1$. Each snake is divided into $L$ parts from head to tail, and each part is either blue or red. For snake $i$, when $i$ is expressed in binary as $i = \sum_{k = 1}^{L} c_k 2^{L - k}$ ($0 \leq c_k \leq 1$),

• if $c_k = 0$, the $k$-th part from the head of snake $i$ is blue,
• if $c_k = 1$, the $k$-th part from the head of snake $i$ is red.

Each snake has a toxicity value, which is an integer between $0$ and $9$. A string $S$ of length $2^L$ consisting of characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 is given, where the $i$-th character ($1 \leq i \leq 2^L$) represents the toxicity of snake $i - 1$.

Due to their quick movements, snakes often escape from JOI Laboratory. Complaints from nearby residents who have witnessed the escaped snakes are frequently received by JOI Laboratory.

You are given information about complaints over $Q$ days. The complaint on day $d$ ($1 \leq d \leq Q$) is represented as a string $T_d$ of length $L$ consisting of 0, 1, ?, where

• if the $j$-th character ($1 \leq j \leq L$) of $T_d$ is 0, it indicates that the $j$-th part from the head of all snakes that escaped on day $d$ is blue,
• if the $j$-th character ($1 \leq j \leq L$) of $T_d$ is 1, it indicates that the $j$-th part from the head of all snakes that escaped on day $d$ is red,
• if the $j$-th character ($1 \leq j \leq L$) of $T_d$ is ?, it indicates that no information was provided about the $j$-th part from the head of the snakes that escaped on day $d$.

All complaints are accurate. Escaped snakes are captured by the staff of JOI Laboratory on the same day. Captured snakes may escape again the next day or later.

To estimate the risk posed by escaped snakes, Chairman K of JOI Laboratory wants to know the total toxicity of snakes that could have escaped. Your task is to write a program that, from the information about complaints over $Q$ days, calculates the total toxicity of snakes that could have escaped each day.

Input Format

Read the following input from standard input:

• The first line contains two integers $L, Q$ separated by a space, representing the number of parts of each snake and the number of days complaints are received, respectively.
• The second line contains a string $S$ of length $2^L$, representing the toxicity of snakes.
• The following $Q$ lines contain a string $T_d$ of length $L$, representing the complaint on day $d$ ($1 \leq d \leq Q$).

Output Format

Output $Q$ lines to standard output. The $d$-th line should contain an integer representing the total toxicity of snakes that could have escaped on day $d$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
10
12
12
36

Sample Input #2

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

Sample Output #2

9
18
38
30
14
15
20
80

Notes/Hints

Task

Given the string $S$ representing the toxicity of snakes and information about complaints over $Q$ days, create a program that calculates the total toxicity of snakes that could have escaped each day.

Note the small memory limit.

Constraints

All input data satisfies the following conditions:

• $1 \leq L \leq 20$.
• $1 \leq Q \leq 1,000,000$.
• $S$ is a string of length $2^L$.
• The string $S$ consists of characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• $T_d$ is a string of length $L$ ($1 \leq d \leq Q$).
• The string $T_d$ consists of characters 0, 1, ? ($1 \leq d \leq Q$).

Subtasks

Subtask 1 [5 points]

Satisfies the following conditions:

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

Subtask 2 [7 points]

• $L \leq 10$.

Subtask 3 [10 points]

• $L \leq 13$.

Subtask 4 [53 points]

• $Q \leq 50,000$.

Subtask 5 [25 points]

• No additional constraints.

Sample Explanation 1

In this example, $L = 3$. There are $2^3 = 8$ snakes divided into 3 parts each. Complaints are received over 5 days.

• On the 1st day, the only possible escaped snake is snake $0$. The total toxicity is $1$.
• On the 2nd day, the possible escaped snakes are snakes $0, 1, 2, 3$. The total toxicity is $10$.
• On the 3rd day, the possible escaped snakes are snakes $4, 6$. The total toxicity is $12$.
• On the 4th day, the possible escaped snakes are snakes $3, 7$. The total toxicity is $12$.
• On the 5th day, the possible escaped snakes are snakes $0, 1, 2, 3, 4, 5, 6, 7$. The total toxicity is $36$.

见题面 Input 部分

见题面 Output 部分