Snake Escaping

JOI Laboratory keeps $2^L$ poisonous snakes, numbered $0, 1, \ldots, 2^L - 1$. Each snake is divided into $L$ parts from the head to the tail, and each part is either blue or red. Write the number of snake $i$ in binary as $i = \sum_{k=1}^{L} c_k 2^{L-k}$ ($0 \le c_k \le 1$). Then

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

Each snake has an integer between $0$ and $9$, inclusive, called its toxicity. You are given a string $S$ of length $2^L$ consisting of the digits $0$ to $9$. The $i$-th character of $S$ ($1 \le i \le 2^L$) is the toxicity of snake $i - 1$.

Snakes are quick, so they often escape from JOI Laboratory. People living near the laboratory file complaints when they see snakes escaping.

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

• If the $j$-th character of $T_d$ ($1 \le j \le L$) is $0$, the $j$-th part of every snake that escaped on the $d$-th day is blue.
• If the $j$-th character of $T_d$ is $1$, the $j$-th part of every snake that escaped on the $d$-th day is red.
• If the $j$-th character of $T_d$ is $?$, nobody reported anything about the $j$-th part of the snakes that escaped on the $d$-th day.

Every complaint is accurate. All snakes that escaped were caught by the laboratory staff on the same day, so the same snake may escape again on a different day.

To estimate the risk of escaping snakes, Professor K, the executive director of JOI Laboratory, wants to know, for each day, the sum of the toxicities of the snakes that might have escaped. That is, for the $d$-th day you must add up the toxicities of all snakes that do not contradict $T_d$.

Given the string $S$ describing the toxicities and the complaints for $Q$ days, write a program that computes, for each day, the sum of the toxicities of the snakes that might have escaped from the laboratory.

Note that the memory limit for this task is small.

Read the following data from standard input.

• The first line contains two integers $L$ and $Q$ separated by a space: the number of parts of each snake and the number of days with complaints.
• The second line contains a string $S$ of length $2^L$ describing the toxicities of the snakes.
• The $d$-th of the following $Q$ lines ($1 \le d \le Q$) contains a string $T_d$ of length $L$, the complaint for the $d$-th day.

Write $Q$ lines to standard output. The $d$-th line must contain one integer: the sum of the toxicities of the snakes that might have escaped on the $d$-th day.

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