#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e6+10;
int a[mxN];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int l, q;
cin >> l >> q;
int n = (1 << l);
vector<int> sub(n+1), sup(n+1), S(n+1), btcnt(n+1);
for(int i = 0; i < n; i++) {
char c; cin >> c;
S[i] = c - '0';
sub[i] = sup[i] = S[i];
btcnt[i] = __builtin_popcount(i);
}
for(int i = 0; i < l; i++) {
for(int m = 0; m < n; m++) {
if(m & (1 << i)) {
sub[m] += sub[m ^ (1 << i)];
}
else {
sup[m] += sup[m ^ (1 << i)];
}
}
}
while(q--) {
string s;
cin >> s;
int A = 0, B = 0, C = 0, cntA = 0, cntB = 0, cntC = 0;
for(int i = 0; i < l; i++) {
int now = (1 << (l - 1 - i));
if(s[i] == '0') {
A |= now;
++cntA;
}
else if(s[i] == '1') {
B |= now;
++cntB;
}
else {
C |= now;
++cntC;
}
}
ll ans = 0;
if(cntA <= cntB && cntA <= cntC) {
for(int m = A; m != 0; m = (m - 1) & A) {
ans += (1 - 2 * (btcnt[m] & 1)) * 1LL * sup[B|m];
}
ans += sup[B];
}
else if(cntC <= cntA && cntC <= cntB) {
for(int m = C; m != 0; m = (m - 1) & C) {
ans += S[B|m];
}
ans += S[B];
}
else {
for(int m = B; m != 0; m = (m - 1) & B) {
int now = (B|C)^m;
ans += (1 - 2 * (btcnt[m] & 1)) * 1LL * sub[now];
}
ans += sub[C|B];
}
cout << ans << '\n';
}
return 0;
}
