#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e5 + 12, mod = 1e9 + 7;
const ll INF = 1e18;
int n, q, w[1 << 20], sub[1 << 20], sup[1 << 20], cnt[1 << 20];
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
int all = (1 << n) - 1;
for(int i = 0;i < (1 << n);i++){
char x; cin >> x, w[i] = x - '0', cnt[i] = __builtin_popcount(i);
sup[i] = sub[all ^ i] = w[i];
}
for(int i = 0;i < n;i++){
for(int j = 0;j < (1 << n);j++){
if((j >> i) & 1)
sup[j] += sup[j ^ (1 << i)];
}
for(int j = 0;j < (1 << n);j++){
if((j >> i) & 1)
sub[j] += sub[j ^ (1 << i)];
}
}
for(int i = 0;i < q;i++){
int A = 0, B = 0, C = 0;
int cA = 0, cB = 0, cC = 0;
for(int j = 1;j <= n;j++){
char x;
cin >> x;
if(x == '0')
cA += 1, A ^= (1 << (n - j));
else if(x == '1')
cB += 1, B ^= (1 << (n - j));
else
cC += 1, C ^= (1 << (n - j));
}
int ans = 0;
if(cA <= cC && cA <= cB){
for(int mask = A;mask >= 0;mask = (mask - 1) & A){
if((cnt[A] - cnt[mask]) & 1)
ans -= sub[mask | C];
else
ans += sub[mask | C];
if(mask == 0)
break;
}
}
else if(cB <= cA && cB <= cC){
for(int mask = B;mask >= 0;mask = (mask - 1) & B){
if((cnt[B] - cnt[mask]) & 1)
ans -= sup[mask | C];
else
ans += sup[mask | C];
if(mask == 0)
break;
}
}
else{
for(int mask = C;mask >= 0;mask = (mask - 1) & C){
ans += w[B | mask];
if(mask == 0)
break;
}
}
cout << ans << "\n";
}
}
