#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif
int main() {
cin.tie(0)->sync_with_stdio(0);
int L, Q;
cin >> L >> Q;
vector<int> t(1 << L);
for (int &i : t) {
char c;
cin >> c;
i = c - '0';
}
auto r = t;
REP (i, 1 << L) {
if (i < (i ^ ((1 << L) - 1))) {
swap(r[i], r[i ^ ((1 << L) - 1)]);
}
}
auto SOS = [&](vector<int> &v) {
REP (i, L) {
REP (j, 1 << L) {
if (j & (1 << i)) {
v[j] += v[j ^ (1 << i)];
}
}
}
};
auto v = t;
SOS(v);
SOS(r);
map<char, int> mp;
mp['0'] = 0;
mp['1'] = 1;
mp['?'] = 2;
REP (i, Q) {
vector<char> w(L);
vector<int> z(3);
for (char &j : w) {
cin >> j;
++z[mp[j]];
}
reverse(w.begin(), w.end());
if (z[0] < 7) {
int odp = 0, bas = 0, msk = 0;
REP (j, L) {
if (w[j] == '?') {
bas ^= 1 << j;
}
else if (w[j] == '0') {
msk ^= 1 << j;
}
}
for (int j = msk; j; j = (j - 1) & msk) {
if (__builtin_parity(msk ^ j)) {
odp -= r[j ^ bas];
}
else {
odp += r[j ^ bas];
}
}
cout << odp + (__builtin_parity(msk) ? -r[bas] : r[bas]) << '\n';
}
else if (z[1] < 7) {
int odp = 0, bas = 0, msk = 0;
REP (j, L) {
if (w[j] == '?') {
bas ^= 1 << j;
}
else if (w[j] == '1') {
msk ^= 1 << j;
}
}
for (int j = msk; j; j = (j - 1) & msk) {
if (__builtin_parity(msk ^ j)) {
odp -= v[j ^ bas];
}
else {
odp += v[j ^ bas];
}
}
cout << odp + (__builtin_parity(msk) ? -v[bas] : v[bas]) << '\n';
}
else {
int odp = 0, bas = 0, msk = 0;
REP (j, L) {
if (w[j] == '?') {
msk ^= 1 << j;
}
else if (w[j] == '1') {
bas ^= 1 << j;
}
}
for (int j = msk; j; j = (j - 1) & msk) {
odp += t[bas ^ j];
}
cout << odp + t[bas] << '\n';
}
}
}
