#pragma GCC optimize("Ofast")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
int x, q;
std::string str;
int dp_subsets[1<<20];
int dp_supersets[1<<20];
void precalc_dp() {
for (int i = 0; i < (1<<x); i++) {
dp_subsets[i] = str[i] - '0';
}
for (int i = 0; i < x; i++) {
for (int mask = 0; mask < (1<<x); mask++) {
if (mask&(1<<i)) {
dp_subsets[mask] += dp_subsets[mask^(1<<i)];
}
}
}
for (int i = 0; i < (1<<x); i++) {
dp_supersets[i] = str[i] - '0';
}
for (int i = 0; i < x; i++) {
for (int mask = (1<<x)-1; mask >= 0; mask--) {
if (!(mask&(1<<i))) {
dp_supersets[mask] += dp_supersets[mask^(1<<i)];
}
}
}
}
int to_decimal(std::string str) {
int ret = 0;
for (int i = 0; i < str.size(); i++) {
ret <<= 1;
ret += (str[i]=='1');
}
return ret;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> q;
std::cin >> str;
precalc_dp();
/*for (int i = 0; i < (1<<x); i++) {
std::cout << i << " " << dp_subsets[i] << " " << dp_supersets[i] << "\n";
}*/
while (q--) {
std::string pattern;
std::cin >> pattern;
int aps[3] = {0};
aps[0] = aps[1] = aps[2] = 0;
for (int i = 0; i < x; i++) {
if (pattern[i] == '0' || pattern[i] == '1') {
aps[pattern[i]-'0'] |= (1<<(x-i-1));
}
else {
aps[2] |= (1<<(x-i-1));
}
}
// min_cnt <= 6
int min_cnt = std::min({
__builtin_popcount(aps[0]),
__builtin_popcount(aps[1]),
__builtin_popcount(aps[2])});
if (__builtin_popcount(aps[2]) == min_cnt) {
int ret = 0;
for (int mask = aps[2]; mask >= 0; mask = (mask-1)&aps[2]) {
for (int i = 0; i < x; i++) {
if (!(aps[2]&(1<<i))) {
continue;
}
if (mask&(1<<i)) {
pattern[x-i-1] = '1';
}
else {
pattern[x-i-1] = '0';
}
}
ret += str[to_decimal(pattern)]-'0';
if (!mask) {
break;
}
}
std::cout << ret << "\n";
}
else if (__builtin_popcount(aps[0]) == min_cnt) {
int ret = 0;
int one_mask = aps[1];
for (int mask = aps[0]; mask >= 0; mask = (mask-1)&aps[0]) {
int sgn = ((__builtin_popcount(mask))&1) ? -1 : 1;
int full_mask = mask | aps[1];
ret += sgn * dp_supersets[full_mask];
if (!mask) {
break;
}
}
std::cout << ret << "\n";
}
else {
int ret = 0;
int question_mask = aps[2];
for (int mask = aps[1]; mask >= 0; mask = (mask-1)&aps[1]) {
int sgn = ((__builtin_popcount(aps[1])-__builtin_popcount(mask))&1) ? -1 : 1;
int full_mask = aps[2] | mask;
ret += sgn * dp_subsets[full_mask];
if (!mask) {
break;
}
}
std::cout << ret << "\n";
}
}
}
