#include <iostream>
#include <array>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
int main() {
int L, Q;
std::cin >> L >> Q;
std::string S;
std::cin >> S;
std::vector<int> sub(1 << L), sup(1 << L);
for (int i = 0; i < 1 << L; i++)
sub[i] = sup[i] = S[i] - '0';
for (int i = 0; i < L; i++) {
for (int mask = 0; mask < 1 << L; mask++) {
if (mask >> i & 1) sub[mask] += sub[mask ^ (1 << i)];
else sup[mask] += sup[mask ^ (1 << i)];
}
}
while (Q--) {
std::string T;
std::cin >> T;
std::reverse(T.begin(), T.end());
std::array<int, 3> freq = {};
int fixed = 0, vary = 0;
for (int i = 0; i < L; i++) {
if (T[i] == '0') {
freq[0]++;
} else if (T[i] == '1') {
freq[1]++;
fixed += 1 << i;
} else {
freq[2]++;
vary += 1 << i;
}
}
std::pair<int, int> mn = {L + 1, 0};
for (int i = 0; i < 3; i++)
mn = std::min(mn, std::make_pair(freq[i], i));
int res = 0;
if (mn.second == 0) {
fixed += vary;
vary = (1 << L) - 1 - vary;
for (int s = fixed; s < 1 << L; ++s |= fixed) {
int sgn = __builtin_popcount(s - fixed) & 1 ? -1 : 1;
res += sgn * sup[s & vary];
}
} else if (mn.second == 1) {
for (int s = fixed; ; --s &= fixed) {
int sgn = __builtin_popcount(fixed - s) & 1 ? -1 : 1;
res += sgn * sub[s | vary];
if (s == 0) break;
}
} else {
for (int s = vary; ; --s &= vary) {
res += S[s + fixed] - '0';
if (s == 0) break;
}
}
std::cout << res << '\n';
}
return 0;
}
