#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;
int s1[(1 << Log) + 2];
int s0[(1 << Log) + 2];
int L, Q;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> L >> Q;
str s;
cin >> s;
for(int i = 0; i < (1 << L); i++) s1[i] = s[i] - '0';
for(int i = 0; i < (1 << L); i++) s0[((1<<L) - 1) ^ i] = s[i] - '0';
for(int l = 0; l < L; l++)
for(int i = 0; i < (1 << L); i++)
if(i >> l & 1) s1[i ^ (1 << l)] += s1[i];
for(int l = 0; l < L; l++)
for(int i = 0; i < (1 << L); i++)
if(i >> l & 1) s0[i ^ (1 << l)] += s0[i];
while(Q --){
cin >> s;
int mk0 = 0, mk1 = 0;
for(int i = 0; i < L; i++){
if(s[i] == '1') mk1 |= (1 << (L - 1 - i));
if(s[i] == '0') mk0 |= (1 << (L - 1 - i));
}
if(__builtin_popcount(mk0) < __builtin_popcount(mk1)){
int res = s1[mk1];
int sub = mk0;
while(sub){
res += (__builtin_popcount(sub) & 1 ? -1 : 1) * s1[sub + mk1];
sub = mk0 & (sub - 1);
}
cout << res << '\n';
} else {
int res = s0[mk0];
int sub = mk1;
while(sub){
res += (__builtin_popcount(sub) & 1 ? -1 : 1) * s0[sub + mk0];
sub = mk1 & (sub - 1);
}
cout << res << '\n';
}
}
return 0;
}
