#include<iostream>
#include<string>
using namespace std;
#include<string>
#include<vector>
#include<algorithm>
#define maxp 1048580
using namespace std;
int st[maxp],n,p,res,zer[maxp], on[maxp], cnt[maxp];
int ab(int x) { return x > 0 ? x : -x; }
void init(int N, int Q, string S) {
n = N; p = 1 << n;
for (int i = 0; i < p; i++) zer[i] = on[i] = st[i] = S[i] - '0';
for (int i = 1; i < p; i<<=1) {
for (int j = 0; j < p; j++) {
if (j & i) zer[j] += zer[j ^ i];
else on[j] += on[j ^ i];
}
}
cnt[0] = 0;
for (int i = 0; i < p/2; i++) {
cnt[i << 1] = cnt[i];
cnt[(i << 1) + 1] = cnt[i] + 1;
}
}
int o[20], z[20], q[20];
int oc, zc, qc;
void rec1(int i, int c, int a) {
if (i == oc) {res += (a^zer[c]) + (a & 1);return;}
rec1(i + 1, c, a);
rec1(i + 1, c ^ o[i], ~a);
}
void rec0(int i, int c, int a) {
if (i == zc) {res += (a^on[c]) + (a&1); return; }
rec0(i + 1, c, a);
rec0(i + 1, c ^ z[i], ~a);
}
void recq(int i, int c) {
if (i == qc) { res += st[c]; return; }
recq(i + 1, c);
recq(i + 1, c ^ q[i]);
}
int query(string A) {
oc = zc = qc = 0;
int a = 0, b = 0, q = 0;
for (int i = 0; i < n; i++) {
if (A[i] == '0') zc++, a+=1<<(n-1-i);
else if (A[i] == '1') oc++, b += 1 << (n - 1 - i);
else qc++, q += 1 << (n - 1 - i);
}
if (oc < zc && oc < qc) {
res = 0;
for (int i = b; i >= 0; i--) {
i &= b;
if (cnt[i | q] & 1) res += zer[i | q];
else res -= zer[i | q];
}
/*int c = 0;
int po = 0;
for (int i = 0; i < n; i++) {
if (A[i] == '1') o[po++] = (1 << (n - 1 - i));
else if(A[i]=='?') c += (1 << (n - 1 - i));
}
rec1(0, c, 0);*/
return ab(res);
}
else if (qc > zc) {
res = 0;
for (int i = a; i >= 0; i--) {
i &= a;
if (cnt[i | b] & 1) res += on[i | b];
else res -= on[i | b];
}
/*int c = 0;
int pz = 0;
for (int i = 0; i < n; i++) {
if (A[i] == '1') c += (1 << (n - 1 - i));
else if (A[i] == '0') z[pz++]=(1 << (n - 1 - i));
}
res = 0;
rec0(0, c, 0);*/
return ab(res);
}
else {
res = 0;
for (int i = q; i >= 0; i--) {
i &= q;
res += st[i | b];
}
/*res = 0;
int c = 0;
int pq = 0;
for (int i = 0; i < n; i++) {
if (A[i] == '1') c += (1 << (n - 1 - i));
else if (A[i] == '?') q[pq++]=(1 << (n - 1 - i));
}
recq(0, c);*/
return res;
}
return 0;
}
/*
4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????
3 5
12345678
000
0??
1?0
?11
???
*/
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, Q; cin >> N >> Q;
string S; cin >> S;
init(N, Q, move(S));
for (int i = 0; i < Q; i++) {
string A;
cin >> A;
cout << query(move(A)) << endl;
}
}
