#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mxn = 1e6;
int super[1<<20], sub[1<<20];
int ind[3][20];
void solve(){
int L,Q; cin >> L >> Q;
string S; cin >> S;
for(int i = 0; i < 1<<L; i++)
super[i] = sub[i] = S[i]-'0';
for(int i = 0; i < L; i++)
for(int j = 0; j < 1<<L; j++)
if(j&(1<<i)) sub[j] += sub[j^(1<<i)];
else super[j] += super[j^(1<<i)];
for(int _ = 0; _ < Q; _++){
string T; cin >> T;
reverse(T.begin(),T.end());
int a = 0, b = 0, c = 0;
for(int i = 0; i < L; i++){
if(T[i]=='0'){
ind[0][a++] = i;
}else if(T[i]=='1'){
ind[1][b++] = i;
}else{
ind[2][c++] = i;
}
}
int mn = min({a,b,c});
if(mn == a){
int sum = 0;
int num = 0;
for(int i = 0; i < L; i++) if(T[i]=='1')
num ^= (1<<i);
for(int mask = 0; mask < 1<<a; mask++){
int dnum = num;
for(int i = 0; i < a; i++) if(mask&(1<<i))
dnum ^= (1<<ind[0][i]);
if(__builtin_popcount(mask)&1) sum -= super[dnum];
else sum += super[dnum];
}
cout << sum << '\n';
}else if(mn == b){
int sum = 0;
int num = 0;
for(int i = 0; i < L; i++) if(T[i]!='0')
num ^= (1<<i);
for(int mask = 0; mask < 1<<b; mask++){
int dnum = num;
for(int i = 0; i < b; i++) if(mask&(1<<i))
dnum ^= (1<<ind[1][i]);
if(__builtin_popcount(mask)&1) sum -= sub[dnum];
else sum += sub[dnum];
}
cout << sum << '\n';
}else{
int sum = 0;
int num = 0;
for(int i = 0; i < L; i++) if(T[i]=='1')
num ^= (1<<i);
for(int mask = 0; mask < 1<<c; mask++){
int dnum = num;
for(int i = 0; i < c; i++) if(mask&(1<<i))
dnum ^= (1<<ind[2][i]);
sum += S[dnum] - '0';
}
cout << sum << '\n';
}
}
}
signed main(){
cin.tie(0)->sync_with_stdio(false);
int t = 1;
while(t--){solve();}
}
