Description

There are $2^L$ poisonous snakes in the JOI laboratory. The snakes are numbered $0,1,\cdots,2^L-1$. Each snake is divided into $L$ segments from head to tail. Each segment is either blue or red. For snake $i$, let $i = \sum_{k=1}^{L} c_k2^{L-k}$ ($0 \leq c_k \leq 1$) be the binary representation of $i$. Then:

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

Each poisonous snake has an integer toxicity between $0$ and $9$, inclusive. You are given a string $S$ of length $2^L$ consisting of $\texttt{0,1,2,3,4,5,6,7,8,9}$. The $i$-th character ($1 \leq i \leq 2^L$) is the toxicity of snake $i-1$.

Because the snakes move quickly, they often escape from the JOI laboratory. People living near the laboratory complain to the JOI laboratory that they saw snakes escaping. You will receive a list of complaints for $Q$ days. The complaint on day $d$ ($1 \leq d \leq Q$) is a string $T_d$ of length $L$ consisting of $\texttt{0,1,?}$.

• If the $j$-th character ($1 \leq j \leq L$) of $T_d$ is $\texttt{0}$, it means that for every snake that escaped from the laboratory on day $d$, its $j$-th segment is blue.
• If the $j$-th character ($1 \leq j \leq L$) of $T_d$ is $\texttt{1}$, it means that for every snake that escaped from the laboratory on day $d$, its $j$-th segment is red.
• If the $j$-th character ($1 \leq j \leq L$) of $T_d$ is $\texttt{?}$, it means that people did not provide information about the $j$-th segment of the snakes that escaped on day $d$.

All complaints are accurate. All snakes that escape from the laboratory are taken in by the laboratory staff on the same day. It is possible that the same snake escapes on different days.

To estimate the risk of snakes escaping, Director Professor K wants to know the total toxicity of the snakes that could have escaped from the laboratory. Your task is to write a program that, based on the list of complaints for $Q$ days, computes for each day the total toxicity of snakes that could have escaped from the laboratory.

Given the string $S$ describing the snakes’ toxicities and the list of complaints for $Q$ days, write a program to compute, for each day, the total toxicity of the snakes that could have escaped.

Input Format

The first line contains two space-separated integers $L$ and $Q$, representing the number of segments of each snake and the number of complaint days. The second line contains a string $S$ of length $2^L$, describing the toxicities of the snakes. The next $Q$ lines each contain a string $T_d$ of length $L$, which is the complaint for day $d$.

Output Format

Output $Q$ lines. The $d$-th line should contain one integer: the total toxicity of the snakes that could have escaped from the laboratory on day $d$.

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

1
10
12
12
36

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

9
18
38
30
14
15
20
80

Hint

Constraints

For $100\%$ of the testdata, $1 \leq L \leq 20$, $1 \leq Q \leq 10^6$, $S$ is a string of length $2^L$ consisting of $\texttt{0,1,2,3,4,5,6,7,8,9}$, and each $T_d$ is a string of length $L$ ($1 \leq d \leq Q$) consisting of $\texttt{0,1,?}$.

• Subtask $1$ ($5$ points): $L \leq 10$, $Q \leq 1000$.
• Subtask $2$ ($7$ points): $L \leq 10$.
• Subtask $3$ ($10$ points): $L \leq 13$.
• Subtask $4$ ($53$ points): $Q \leq 5000$.
• Subtask $5$ ($25$ points): no additional constraints.

Sample Explanation

For Sample $1$: $L=3$, so there are $2^3=8$ poisonous snakes, and each is divided into $3$ segments. There are $5$ days of complaints.

• On the first day, the only snake that could have escaped is snake $0$. The total toxicity is $1$.
• On the second day, the snakes that could have escaped are snakes $0,1,2,3$. The total toxicity is $10$.
• On the third day, the snakes that could have escaped are snakes $4,6$. The total toxicity is $12$.
• On the fourth day, the snakes that could have escaped are snakes $3,7$. The total toxicity is $12$.
• On the fifth day, the snakes that could have escaped are snakes $0,1,2,3,4,5,6,7$. The total toxicity is $36$.

Problem Notes

This problem is from T5: Snake Escaping in the Final Round of The 17th Japanese Olympiad in Informatics (JOI 2017/2018).
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5