#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>
using namespace std;
const int BIT = 20;
int f[1<<BIT], g[1<<BIT], h[1<<BIT], ans;
void solve2(int i, vector<int> &v, int val) {
if (i==v.size()) {
ans += h[val];
return;
}
val &= ~(1<<v[i]);
solve2(i+1,v,val);
val |= (1<<v[i]);
solve2(i+1,v,val);
}
void solve1(int i, vector<int> &v, int val, int cnt) {
if (i==v.size()) {
if (cnt==0) return;
if (cnt%2) {
ans -= f[val];
}
else {
ans += f[val];
}
return;
}
val |= (1<<v[i]);
solve1(i+1,v,val,cnt);
val &= ~(1<<v[i]);
solve1(i+1,v,val,cnt+1);
}
void solve0(int i, vector<int> &v, int val, int cnt) {
if (i==v.size()) {
if (cnt==0) return;
if (cnt%2) {
ans -= g[val];
}
else {
ans += g[val];
}
return;
}
val |= (1<<v[i]);
solve0(i+1,v,val,cnt+1);
val &= ~(1<<v[i]);
solve0(i+1,v,val,cnt);
}
void solve() {
int n,q; cin >> n >> q;
for (int i =0; i < (1<<n); i++) {
char c; cin >> c;
f[i] += c - '0';
g[i] += c - '0';
h[i] += c - '0';
// cerr << "cin >> " << bitset<5>(i) << " :" << c << endl;
}
for (int i = 0; i < n; i++) {
for (int x = 0; x < (1<<n); x++) {
if (x&(1<<i)) f[x] += f[x^(1<<i)];
else g[x] += g[x^(1<<i)];
}
}
for (int i = 0; i < q; i++) {
string s; cin >> s;
reverse(s.begin(), s.end());
int cnt = 0, val = 0, val2 = 0,val1 = 0;
vector<int> v1,v2,v0;
for (char c : s) {
if (c!='0') {
val |= (1<<cnt);
if (c=='1') {
val2 |= (1<<cnt);
v1.push_back(cnt);
}
else {
v2.push_back(cnt);
val1 |= (1<<cnt);
}
}
else {
v0.push_back(cnt);
}
cnt++;
}
if (v2.size() <= v1.size() && v2.size() <= v0.size()) {
ans = 0;
solve2(0,v2,val);
}
else if (v1.size() <= v2.size() && v1.size() <= v0.size()) {
ans = f[val];
solve1(0,v1,val,0);
}
else {
ans = g[val2];
solve0(0,v0,val2,0);
}
cout << ans << '\n';
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
return 0;
}
