import java.io.*;
import java.util.*;
public class snake_escaping {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) { e.printStackTrace(); }
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
}
public static class Pair implements Comparable<Pair> {
int vtx;
int val;
public Pair(int a, int b) {
this.vtx = a;
this.val = b;
}
public int compareTo(Pair other) {
if (this.val < other.val) return -1;
if (this.val > other.val) return 1;
if (this.vtx < other.vtx) return -1;
return 1;
}
}
static int MOD = 998244353;
public static void main(String[] args) {
FastReader br = new FastReader();
int L = br.nextInt();
int Q = br.nextInt();
final int[] S = new int[1 << L];
final int[] sup = new int[1 << L];
final int[] sub = new int[1 << L];
final int[] btcnt = new int[1 << L]; // Precompute bitcount to speed up
String s = br.next();
for (int i = 0; i < (1 << L); i++) {
S[i] = (int)s.charAt(i) - '0';
sup[i] = sub[i] = S[i];
btcnt[i] = Integer.bitCount(i);
}
// SOS DP!!
for (int b = 0; b < L; b++) {
for (int m = 0; m < (1 << L); m++) {
if (((m >>> b) & 1) == 0) {
sup[m] += sup[m ^ (1 << b)];
} else {
sub[m] += sub[m ^ (1 << b)];
}
}
}
StringBuilder sb =
new StringBuilder(); // I'm using stringbuilder to reduce the
// number of times I print because calling
// System.out.println 10^6 times is slow
int A;
int B;
int C;
int ca;
int cb;
int cc;
long ans;
for (int i = 0; i < Q; i++) {
s = br.next();
A = 0;
B = 0;
C = 0;
ca = 0;
cb = 0;
cc = 0;
ans = 0;
for (int j = 0; j < L; j++) {
if (s.charAt(j) == '0') {
A |= (1 << (L - j - 1));
ca++;
} else if (s.charAt(j) == '1') {
B |= (1 << (L - j - 1));
cb++;
} else {
C |= (1 << (L - j - 1));
cc++;
}
}
if (ca <= cb && ca <= cc) {
for (int m = A; m != 0; m = (m - 1) & A) {
ans += (1 - 2 * ((btcnt[m]) & 1)) * sup[B | m];
}
ans += sup[B];
} else if (cb <= ca && cb <= cc) {
for (int m = B; m != 0; m = (m - 1) & B) {
ans += (1 - 2 * ((btcnt[m]) & 1)) * sub[C | (B ^ m)];
}
ans += sub[C | B];
} else {
for (int m = C; m != 0; m = (m - 1) & C) { ans += S[m | B]; }
ans += S[B];
}
sb.append(ans).append("\n");
if ((i & ((1 << 17) - 1)) == 0) { // sb can have a lot of memory
System.out.println(sb.toString());
sb = new StringBuilder();
}
}
System.out.println(sb.toString());
}
}
