#include <bits/stdc++.h>
#define pu push
#define pf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define SET_OFF(x, i) ((x)&~MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 1100000;
const int inf = (int)1e9+7;
using namespace std;
template<class T1, class T2>
bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}
int L, Q;
int poison[MAX_SIZE], sup[MAX_SIZE], sub[MAX_SIZE], cntbit[MAX_SIZE];
string s;
void init(){
cin>>L>>Q>>s;
}
void ilovesunshine(){
init();
for (int mask=0; mask<MASK(L); mask++){
poison[mask] = s[mask]-'0';
sup[mask] = sub[mask] = poison[mask];
cntbit[mask] = c_bit(mask);
}
for (int i=0; i<L; i++){
for (int mask=0; mask<MASK(L); mask++){
if (!BIT(mask, i)){
sup[mask]+=sup[mask^(1<<i)];
}
else sub[mask]+=sub[mask^(1<<i)];
}
}
while (Q--){
cin>>s;
// cout<<s<<"\n";
int A=0, B=0, C=0, ca=0, cb=0, cc=0; ll res=0;
for (int i=0; i<L; i++){
if (s[i]=='0'){
A=SET_ON(A, L-i-1);
ca++;
}
else if (s[i]=='1'){
B=SET_ON(B, L-i-1);
cb++;
}
else{
C=SET_ON(C, L-i-1);
cc++;
}
}
if (ca<=cb && ca<=cc){
for (int s=A; s!=0; s=(s-1)&A){
res += (1-2*((cntbit[s])&1))*sup[B|s];
}
res+=sup[B];
}
else if (cb<=ca && cb<=cc){
for (int s=B; s!=0; s=(s-1)&B){
res += (1-2*((cntbit[s])&1))*sub[C|(B^s)];
}
res+=sub[C|B];
}
else{
for (int s=C; s!=0; s=(s-1)&C){
res+=poison[s|B];
}
res+=poison[B];
}
cout<<res<<"\n";
}
// for (int mask=0; mask<MASK(L); mask++){
// cout<<poison[mask]<<' '<<sup[mask]<<' '<<sub[mask]<<' '<<cntbit[mask]<<"\n";
// }
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("bdbang.INP", "r", stdin);
// freopen("bdbang.OUT", "w", stdout);
ilovesunshine();
return 0;
}
