JOI Laboratory has $2^L$ poisonous snakes. The snakes are numbered $0,1,\dots ,2^L-1$. Each snake is divided into $L$ parts from the head to the tail. The color of each part is either blue or red. For the poisonous snake $i$, let $i=\sum _{k=1}^L{c}_k{2}^{L-k}$ ($0\le c_k\le 1$) be the binary expression of $i$. Then,

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

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

Since poisonous snakes are quick, they often escape from JOI Laboratory. Complaints are given to JOI Laboratory by people living near the laboratory who saw poisonous snakes escaping from the laboratory.

You are given a list of complaints for $Q$ days. The complaints for the $d$-th day ($1\le d\le Q$) is a string $T_d$ of length $L$ consisting of 0, 1, ?.

• If the $j$-th character ($1\le j\le L$) of $T_d$ is 0, this means the $j$-th part of every poisonous snake escaping from the laboratory on the $d$-th day is blue,
• If the $j$-th character ($1\le j\le L$) of $T_d$ is 1, this means the $j$-th part of every poisonous snake escaping from the laboratory on the $d$-th day is red, and
• If the $j$-th character ($1\le j\le L$) of $T_d$ is ?, this means no information was given by people concerning the $j$-th part of poisonous snakes escaping from the laboratory on the $d$-th day.

All the complaints are precise information. All the poisonous snakes escaping from the laboratory were kept by the staff of JOI Laboratory on the same day. It may happen that the same snake escapes on a different day.

In order to estimate the risk of escaping poisonous snakes, Professor K, the executive director of JOI Laboratory, wants to know the sum of toxicities of the snakes which might escape from the laboratory. Your task is to write a program which calculates, given the list of complaints for $Q$ days, the sum of toxicities of the snakes which might escape from the laboratory for each day.

Input Specification

The first line contains two space separated integers $L,Q$. They are the number of parts of each poisonous snake and the number of days for the complaints, respectively.

The second line contains a string $S$ of length $2^L$. It describes the toxicities of the poisonous snakes.

Each of the following $Q$ lines contains a string $T_d$ of length $L$. It is the complaints of the $d$-th day.

Output Specification

Write $Q$ lines to the standard output. The $d$-th line should contain an integer, the sum of toxicities of the snakes which might escape from the laboratory on $d$-th day.

Constraints

In all test cases,

• $1\le L\le 20$, $1\le Q\le {10}^6$
• $S$ is a string of length $2^L$ and consists of digits from $0$ to $9$
• $T_d$ is a string of length $L$ and consists of 0, 1, and ?.

In $5\mathrm{\%}$ test cases, $L\le 10$, $Q\le 1000$.

In another $7\mathrm{\%}$ test cases, $L\le 10$.

In another $10\mathrm{\%}$ test cases, $L\le 13$.

In another $53\mathrm{\%}$ test cases, $Q\le 5\times {10}^4$.

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