#include "bits/stdc++.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
int pw[15], n, q;
string transform(int mask){
string res = "";
for(int i = n - 1; i >= 0; i--){
if(mask >= 2 * pw[i]){
res.push_back('?');
mask -= 2 * pw[i];
}
else if(mask >= pw[i]){
res.push_back('1');
mask -= pw[i];
}
else res.push_back('0');
}
reverse(all(res));
return res;
}
int Shrink(string mask){
int res = 0;
for(int i = 0; i < n; i++){
if(mask[i] == '?') res += pw[i] * 2;
else if(mask[i] == '1') res += pw[i];
}
return res;
}
void _(){
cin >> n >> q;
pw[0] = 1;
for(int i = 1; i < 15; i++) pw[i] = pw[i-1] * 3;
string s;
cin >> s;
int cost[1<<n];
for(int i = 0; i < (1<<n); i++) cost[i] = s[i] - '0';
if(n <= 13){
long long dp[pw[n]];
memset(dp,0,sizeof(dp));
for(int i = 0; i < (1<<n); i++){
int nw = 0;
for(int j = 0; j < n; j++){
if(i>>j&1) nw += pw[j];
}
dp[nw] = cost[i];
}
for(int i = 0; i < pw[n]; i++){
string cur = transform(i);
for(int j = n - 1; j >= 0; j--){
if(cur[j] == '?'){
dp[i] = dp[i - pw[j]] + dp[i - 2 * pw[j]];
break;
}
}
}
while(q--){
string cur;
cin >> cur;
reverse(all(cur));
int mask = Shrink(cur);
cout << dp[mask] << '\n';
}
}
else{
vector<long long> Ans(q, 0);
vector<int> Mask(q, 0), Mask1(q, 0), Mask2(q, 0);
long long dp[pw[n - 7]];
int Nw[1<<(n-7)], Transition[pw[n - 7]];
memset(Transition, -1, sizeof(Transition));
for(int i = 0; i < pw[n - 7]; i++){
string cur = transform(i);
for(int j = n - 8; j >= 0; j--){
if(cur[j] == '?'){
Transition[i] = j;
break;
}
}
}
for(int i = 0; i < (1 << (n - 7)); i++){
int nw = 0;
for(int j = 0; j < n - 7; j++) if(i>>j&1) nw += pw[j];
Nw[i] = nw;
}
for(int i = 0; i < q; i++){
string snake; cin >> snake;
reverse(all(snake));
for(int j = 0; j < n - 7; j++){
if(snake[j] == '1') Mask[i] += pw[j];
else if(snake[j] == '?') Mask[i] += 2 * pw[j];
}
for(int j = n - 7; j < n; j++){
if(snake[j] == '1'){
Mask1[i] += (1 << j);
Mask2[i] += (1 << j);
}
else if(snake[j] == '?') Mask1[i] += (1 << j);
}
}
for(int lf = 0; lf < 128; lf++){ // son 8 biti fixle
memset(dp,0,sizeof(dp));
int left = 0;
for(int i = n - 7; i < n; i++){
int hm = i - (n - 7);
if(lf>>hm&1) left += (1<<i);
}
for(int i = 0; i < (1 << (n - 7)); i++) dp[Nw[i]] = cost[i + left];
for(int i = 0; i < pw[n - 7]; i++){
if(Transition[i] == -1) continue;
int j = Transition[i];
dp[i] = dp[i - pw[j]] + dp[i - 2 * pw[j]];
}
for(int i = 0; i < q; i++){
int val1 = (Mask1[i] ^ left);
int val2 = (Mask2[i] ^ left);
if(val1 & val2) continue;
Ans[i] += dp[Mask[i]];
}
}
for(int i = 0; i < q; i++) cout << Ans[i] << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
