Poisonous Snake Escape

JOI Laboratory has \(2^L\) poisonous snakes numbered \(0,1,\ldots,2^L-1\). Each snake is divided into \(L\) segments from head to tail. For snake \(i\), represent \(i\) in binary as

\( i = \sum_{k=1}^{L} c_k 2^{L-k} \), where \(c_k \in \{0,1\}\). Then:

• If \(c_k=0\), the \(k\)th segment (from the head) is blue.
• If \(c_k=1\), the \(k\)th segment is red.

Every snake has a toxicity, which is an integer between 0 and 9 (inclusive). You are given a string \(S\) of length \(2^L\) composed of digits 0 through 9; the \(i\)th character (1-indexed) represents the toxicity of snake \(i-1\).

For \(Q\) days, a complaint is received. On day \(d\), the complaint is a string \(T_d\) of length \(L\) consisting of characters '0', '1', and '?'. For each position \(j\) (1-indexed):

• If \(T_d[j]\) is '0', then every snake that escaped that day has its \(j\)th segment blue.
• If \(T_d[j]\) is '1', then every snake that escaped that day has its \(j\)th segment red.
• If \(T_d[j]\) is '?', no information is provided about the \(j\)th segment.

All complaint information is accurate and all snakes captured on a given day were taken in together (note that the same snake might escape on multiple days). Professor K wants to estimate the risk, so for each day, he needs the sum of the toxicities of all snakes that could have escaped that day.

Your task is to write a program that, given the toxicity string \(S\) and \(Q\) days of complaints, computes the possible total toxicity for each day.

inputFormat

The input is given as follows:

L Q
S
T1
T2
...
TQ

Here, \(L\) is the number of segments per snake, and \(S\) is a string of length \(2^L\) where the \(i\)th character represents the toxicity of snake \(i-1\). Each of the following \(Q\) lines contains a complaint string \(T_d\) of length \(L\) consisting only of the characters '0', '1', and '?'.

outputFormat

For each complaint (day), output a single line containing the sum of toxicities of all snakes that match the complaint's color pattern.

No extra spaces or blank lines should be printed.

sample

2 3
0123
0?
?1
??

1
4
6

</p>