#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 20;
ll dp[1 << N], dp2[1 << N];
ll cnt[256];
void get_locs(string &t, vector<ll> &loc, ll &val, char ch, bool q) {
for (ll i = 0; i < t.length(); ++i) {
if (t[i] == ch) {
loc.push_back(t.length() - i - 1);
}
val += (1 << (t.length() - i - 1)) * (t[i] == '1' || (q && t[i] == '?'));
}
}
void populate(queue<pair<ll, ll>> &q, vector<ll> &loc, ll val, ll n) {
q.push({val, -1});
for (ll i = 0; i < n; ++i) {
ll sz = q.size();
while (sz--) {
ll v = q.front().first;
ll idx = q.front().second + 1;
q.pop();
q.push({v, idx});
v ^= (1 << loc[idx]);
q.push({v, idx});
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll l, q;
cin >> l >> q;
string s;
cin >> s;
for (ll i = 0; i < s.length(); ++i) {
dp[i] = dp2[i] = s[i] - '0';
}
for (ll i = 0; i < N; ++i) {
for (ll mask = 0; mask < (1 << N); ++mask) {
if (mask & (1 << i)) {
dp[mask] += dp[mask ^ (1 << i)];
} else {
dp2[mask] += dp2[mask ^ (1 << i)];
}
}
}
while (q--) {
string t;
cin >> t;
ll ans = 0;
cnt['1'] = cnt['0'] = cnt['?'] = 0;
for (auto &i : t) {
cnt[i]++;
}
vector<ll> loc;
queue<pair<ll, ll>> q;
ll val = 0;
if (cnt['?'] <= 6) {
get_locs(t, loc, val, '?', false);
populate(q, loc, val, cnt['?']);
while (!q.empty()) {
ll v = q.front().first;
q.pop();
ans += s[v] - '0';
}
} else if (cnt['1'] <= 6) {
get_locs(t, loc, val, '1', true);
populate(q, loc, val, cnt['1']);
while (!q.empty()) {
ll v = q.front().first;
q.pop();
ans +=
dp[v] *
((__builtin_popcount(v) - cnt['?']) % 2 == cnt['1'] % 2 ? 1 : -1);
}
} else {
get_locs(t, loc, val, '0', false);
populate(q, loc, val, cnt['0']);
while (!q.empty()) {
ll v = q.front().first;
q.pop();
ans += dp2[v] * ((__builtin_popcount(v) - cnt['1']) % 2 == 0 ? 1 : -1);
}
}
cout << ans << "\n";
}
}
