#include <bits/stdc++.h>
#define MASK(x) (1LL<<(x))
#define endl '\n'
using namespace std;
const int MX = MASK(20) + 5;
int n, q;
string a;
int f1[MX];
int f2[MX];
void nhap(){
cin >> n >> q;
cin >> a;
}
void solve(){
for(int i=0; i<MASK(n); i++){
f1[i] = f2[i] = a[i] - '0';
}
for(int i=0; i<n; i++){
for(int mask=0; mask<MASK(n); mask++){
if(mask&MASK(i)) f2[mask] += f2[mask^MASK(i)];
else f1[mask] += f1[mask^MASK(i)];
}
}
while(q--){
string s; cin >> s;
int m0 = 0;
int m1 = 0;
int m2 = 0;
for(char c: s){
m0 = (m0 << 1) | (c == '0'? 1 : 0);
m1 = (m1 << 1) | (c == '1'? 1 : 0);
m2 = (m2 << 1) | (c == '?'? 1 : 0);
}
#define cntbit(x) __builtin_popcount(x)
int ans = 0;
if(cntbit(m0) < 7){
for(int mask=m0; ; mask=(mask - 1)&m0){
ans += cntbit(mask)&1? -f1[m1|mask] : f1[m1|mask];
if(mask == 0) break;
}
}
else if(cntbit(m1) < 7){
for(int mask=m1; ; mask=(mask - 1)&m1){
ans += (cntbit(m1) - cntbit(mask))&1? -f2[m2|mask] : f2[m2|mask];
if(mask == 0) break;
}
}
else if(cntbit(m2) < 7){
for(int mask=m2; ; mask=(mask - 1)&m2){
ans += a[mask|m1] - '0';
if(mask == 0) break;
}
}
cout << ans << endl;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
nhap();
solve();
return 0;
}
