#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
const ll MAXN = 1.1E6;
ll dp1[MAXN], dp0[MAXN];
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll n, Q;
cin >> n >> Q;
ll ALL = (1<<n)-1;
string str;
cin >> str;
for (ll i = 0; i <= ALL; i++)
dp1[i] = str[i]-'0';
for (ll bit = 0; bit < n; bit++)
for (int mask = 0; mask <= ALL; mask++)
if (mask>>bit&1) dp1[mask] += dp1[mask ^ (1<<bit)];
for (ll i = 0; i <= ALL; i++)
dp0[i] = str[i ^ ALL]-'0';
for (ll bit = 0; bit < n; bit++)
for (int mask = 0; mask <= ALL; mask++)
if (mask>>bit&1) dp0[mask] += dp0[mask ^ (1<<bit)];
while (Q--) {
string q;
cin >> q;
reverse(q.begin(), q.end());
int nul = 0, unu = 0, dem;
for (ll i = 0; i < n; i++) nul |= (q[i] == '0') << i;
for (ll i = 0; i < n; i++) unu |= (q[i] == '1') << i;
dem = ALL ^ nul ^ unu;
if (count(q.begin(), q.end(), '?') <= 6) {
ll ans = 0;
for (int mask = 0; mask <= ALL; mask++) {
mask |= unu | nul;
ans += str[mask ^ nul]-'0';
}
cout << ans << '\n';
continue;
}
if (count(q.begin(), q.end(), '0') <= 6) {
ll ans = 0;
for (int mask = nul; ; mask--, mask &= nul) {
bool addSub = __builtin_popcountll(mask ^ nul)%2 == 0;
ans += (addSub ? 1 : -1) * dp0[dem | mask];
if (!mask) break;
}
cout << ans << '\n';
continue;
}
if (count(q.begin(), q.end(), '1') <= 6) {
ll ans = 0;
for (int mask = unu; ; mask--, mask &= unu) {
bool addSub = __builtin_popcountll(mask ^ unu)%2 == 0;
ans += (addSub ? 1 : -1) * dp1[dem | mask];
if (!mask) break;
}
cout << ans << '\n';
continue;
}
assert(false);
}
return 0;
}
/*
????? - ????0
= ????1
????? - ???00
= ???01
+ ???10
+ ???11
????? = ???00 + ???01 + ???10 + ???11
00??? = 00?00 + 00?01 + 00?10 + 00?11
iterate over all subsets of 1's, lets call it 'mask'
check the parity of 'mask^unu' and subtract/add accordingly:
0: subtract
1: add
what you work with is dp[maskQM^mask]
??????????
+dp1111111111
=
+ ???????000
+dp1111111000
+ ???????001
+dp1111111001
-dp1111111000
+ ???????010
+dp1111111010
-dp1111111000
+ ???????011
+dp1111111011
-dp1111111001
-dp1111111010
+dp1111111000
+ ???????100
+dp1111111100
-dp1111111000
+ ???????101
+dp1111111101
-dp1111111001
-dp1111111100
+dp1111111000
+ ???????110
+dp1111111110
-dp1111111010
-dp1111111100
+dp1111111000
+ ???????111
+dp1111111111
-dp1111111011
-dp1111111101
-dp1111111110
+dp1111111001
+dp1111111010
+dp1111111100
-dp1111111000
// tallied up
+ ???????000
+ ???????001
+ ???????010
+ ???????011
+ ???????100
+ ???????101
+ ???????110
+ ???????111
=
+dp1111111111
//
-dp1111111111
+dp1111111011
+dp1111111101
+dp1111111110
-dp1111111001
-dp1111111010
-dp1111111100
+dp1111111000
// AHAHAHAHAH TEHWYW WEOUHWEOYHWE HUWHYYYYW HYYY WHYYYY WHYY TOAEUNOAEUNOHEUNSHOASENU HOANEHUOMG OMG WYH
+ ???????111
-dp1111111111
+dp1111111011
+dp1111111101
+dp1111111110
-dp1111111001
-dp1111111010
-dp1111111100
+dp1111111000
*/
