#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("popcnt")
const int B = 20;
int dp[1 << B], dq[1 << B], arr[1 << B];
int n, q;
int main () {
cin >> n >> q;
for (int i = 0; i < (1 << n); i++) {
char s; cin >> s; int x = s - '0';
arr[i] = dp[i] = dq[i] = x;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < (1 << n); j++) {
if (!(j & (1 << i))) dq[j] += dq[j ^ (1 << i)];
}
for (int j = (1 << n) - 1; j >= 0; j--) {
if (j & (1 << i)) dp[j] += dp[j ^ (1 << i)];
}
}
while (q--) {
string s; cin >> s;
int a = 0, b = 0, c = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
a ^= 1 << (n - i - 1);
} else if (s[i] == '1') {
b ^= 1 << (n - i - 1);
} else {
c ^= 1 << (n - i - 1);
}
}
int ret = 0;
if (__builtin_popcount(a) <= 6) {
int m = a;
while (true) {
if (__builtin_popcount(m) & 1) {
ret -= dq[b | m];
} else {
ret += dq[b | m];
}
if (m == 0) break;
m = (m - 1) & a;
}
} else if (__builtin_popcount(b) <= 6) {
int m = b;
while (true) {
if (__builtin_popcount(m) & 1) {
ret -= dp[c | m];
} else {
ret += dp[c | m];
}
if (m == 0) break;
m = (m - 1) & b;
}
} else {
int m = c;
while (true) {
ret += arr[b ^ m];
if (m == 0) break;
m = (m - 1) & c;
}
}
cout << (ret < 0 ? -ret : ret) << '\n';
}
}
