#include<bits/stdc++.h>
using namespace std;
const int MAX = (int) 2e6;
#define pb push_back
int l, q;
string s;
int a[MAX + 5];
int f[1 << 21], g[1 << 21];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> l >> q;
cin >> s;
for(int i = 0; i < (1 << l); ++i) a[i] = s[i] - '0';
for(int i = 0; i < (1 << l); ++i) f[i] = a[i];
for(int i = 1; i <= l; ++i)
for(int mask = 0; mask < (1 << l); ++mask) if(mask >> (i - 1) & 1) f[mask] += f[mask ^ (1 << (i - 1))];
for(int i = 0; i < (1 << l); ++i) g[(1 << l) - i - 1] = a[i];
for(int i = 1; i <= l; ++i)
for(int mask = 0; mask < (1 << l); ++mask) if(mask >> (i - 1) & 1) g[mask] += g[mask ^ (1 << (i - 1))];
reverse(g, g + (1 << l));
while(q--) {
string t;
cin >> t;
vector<int> v0, v1, v2;
int cur = 0;
int cur2 = 0;
for(int i = l - 1; i >= 0; --i) if(t[i] == '0') v0.pb((1 << (l - i - 1)));
else if(t[i] == '1') v1.pb(1 << (l - i - 1)), cur += (1 << (l - i - 1));
else v2.pb((1 << (l - i - 1))), cur2 += 1 << (l - i - 1);
cur2 += cur;
int ds = 0;
if(v0.size() <= 6) {
int m = v0.size();
for(int mask = 0; mask < (1 << m); ++mask) {
int hs = 1;
if(__builtin_popcount(mask) % 2) hs = -1;
int A = 0;
for(int i = 0; i < m; ++i) if(mask >> i & 1) {
A += v0[i];
}
ds += hs * g[cur + A];
}
cout << ds << "\n";
}
else
if(v1.size() <= 6) {
int m = v1.size();
for(int mask = 0; mask < (1 << m); ++mask) {
int hs = 1;
if(__builtin_popcount(mask) % 2) hs = -1;
int A = 0;
for(int i = 0; i < m; ++i) if(mask >> i & 1) {
A += v1[i];
}
ds += hs * f[cur2 - A];
}
cout << ds << "\n";
}
else {
int m = v2.size();
for(int mask = 0; mask < (1 << m); ++mask) {
int A = 0;
for(int i = 0; i < m; ++i) if(mask >> i & 1)
A += v2[i];
ds += a[A + cur];
}
cout << ds << "\n";
}
}
}
