#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
constexpr int MAX_BIT = 20;
constexpr int MAX_N = 1 << 20;
constexpr int MAGIC = 6;
int dp_sub[MAX_N];
int dp_super[MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k, q;
cin >> k >> q;
string s;
cin >> s;
for (int mask = 0; mask < (1 << k); ++mask) {
dp_sub[mask] = s[mask] - '0';
dp_super[mask] = s[mask] - '0';
}
for (int bit = 0; bit < k; ++bit) {
for (int mask = 0; mask < (1 << k); ++mask) {
if (mask & (1 << bit)) {
dp_sub[mask] += dp_sub[mask ^ (1 << bit)];
} else {
dp_super[mask] += dp_super[mask ^ (1 << bit)];
}
}
}
while (q--) {
string t;
cin >> t;
reverse(t.begin(), t.end());
int cnt_null = 0;
int cnt_one = 0;
int cnt_mark = 0;
int mask_null = 0;
int mask_one = 0;
int mask_mark = 0;
for (int i = 0; i < k; ++i) {
if (t[i] == '0') {
++cnt_null;
mask_null |= 1 << i;
} else if (t[i] == '1') {
++cnt_one;
mask_one |= 1 << i;
} else {
++cnt_mark;
mask_mark |= 1 << i;
}
}
int res = 0;
if (cnt_null <= MAGIC) {
res = dp_super[mask_one];
for (int submask = mask_null; submask > 0; submask = (submask - 1) & mask_null) {
int sign = (__builtin_popcount(submask) % 2 == 0 ? 1 : -1);
res += dp_super[submask | mask_one] * sign;
}
} else if (cnt_one <= MAGIC) {
res = dp_sub[mask_mark | mask_one];
for (int submask = mask_one; submask > 0; submask = (submask - 1) & mask_one) {
int sign = (__builtin_popcount(submask) % 2 == 0 ? 1 : -1);
res += dp_sub[(submask ^ mask_one) | mask_mark] * sign;
}
} else {
res = s[mask_one] - '0';
for (int submask = mask_mark; submask > 0; submask = (submask - 1) & mask_mark) {
res += s[submask | mask_one] - '0';
}
}
cout << res << '\n';
}
return 0;
}
