// File A.cpp created on 11.09.2025 at 15:00:22
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int L, Q;
std::cin >> L >> Q;
std::vector<i64> A(1 << L);
for (int i = 0; i < (1 << L); ++i) {
char c;
std::cin >> c;
A[i] = i64(c - '0');
}
std::vector<i64> f = A;
for (int i = 1; i < (1 << L); i <<= 1) {
for (int j = 0; j < (1 << L); j += i << 1) {
for (int k = 0; k < i; ++k) {
f[i + j + k] += f[j + k];
}
}
}
std::vector<i64> g = A;
for (int i = 1; i < (1 << L); i <<= 1) {
for (int j = 0; j < (1 << L); j += i << 1) {
for (int k = 0; k < i; ++k) {
g[j + k] += g[i + j + k];
}
}
}
debug(f);
debug(g);
std::vector<int> popcnt(1 << L);
for (int i = 0; i < (1 << L); ++i) {
popcnt[i] = 1 - 2 * __builtin_parity(i);
}
while (Q--) {
std::string S;
std::cin >> S;
std::reverse(S.begin(), S.end());
int msk0 = 0, msk1 = 0, mskq = 0;
int cnt0 = 0, cnt1 = 0, cntq = 0;
for (int i = 0; i < L; ++i) {
if (S[i] == '0') {
msk0 |= 1 << i;
cnt0 += 1;
} else if (S[i] == '1') {
msk1 |= 1 << i;
cnt1 += 1;
} else {
mskq |= 1 << i;
cntq += 1;
}
}
i64 ans = 0;
if (cnt0 <= cnt1 && cnt0 <= cntq) {
for (int m = msk0; ; m = m & (m - 1)) {
ans += popcnt[msk0 ^ m] * g[((1 << L) - 1) ^ (mskq | m)];
if (m == 0) {
break;
}
}
} else if (cnt1 <= cnt0 && cnt1 <= cntq) {
for (int m = msk1; ; m = m & (m - 1)) {
ans += popcnt[msk1 ^ m] * f[mskq | m];
if (m == 0) {
break;
}
}
} else {
for (int m = mskq; ; m = m & (m - 1)) {
ans += A[msk1 | m];
if (m == 0) {
break;
}
}
}
std::cout << ans << '\n';
}
return 0;
}
