#include <bits/stdc++.h>
using namespace std;
const int Nmax = (1<<20);
int n, q;
string Val;
int val[Nmax], up[Nmax], down[Nmax], bits[Nmax];
void precalc()
{
int i, j;
for(i=0; i<(1<<n); ++i)
bits[i] = __builtin_popcount(i), up[i] = down[i] = val[i] = Val[i] - '0';
for(i=0; i<n; ++i)
for(j=0; j<(1<<n); ++j)
if(j & (1<<i))
up[j ^ (1<<i)] += up[j];
else down[j ^ (1<<i)] += down[j];
}
int solveQ(int mask, int que)
{
int i, ans = 0;
for(i=que; ; i = (i-1) & que)
{
ans += val[i ^ mask];
if(i == 0) return ans;
}
}
int solve0(int mask0, int mask1, int maskq)
{
int i, ans = 0;
for(i=mask0; ; i = (i-1) & mask0)
{
if(bits[i] & 1) ans -= up[mask1 ^ i];
else ans += up[mask1 ^ i];
if(i == 0) return ans;
}
}
int solve1(int mask0, int mask1, int maskq)
{
int i, ans = 0;
for(i=mask1; ; i = (i-1) & mask1)
{
if(bits[i] & 1) ans -= down[maskq ^ mask1 ^ i];
else ans += down[maskq ^ mask1 ^ i];
if(i == 0) return ans;
}
}
int query()
{
string S;
cin >> S;
reverse(S.begin(), S.end());
int i, mask0 = 0, mask1 = 0, maskq = 0;
for(i=0; i<n; ++i)
{
if(S[i] == '0') mask0 ^= (1<<i);
else if(S[i] == '1') mask1 ^= (1<<i);
else maskq ^= (1<<i);
}
if(bits[maskq] <= bits[mask0] && bits[maskq] <= bits[mask1]) return solveQ(mask1, maskq);
else if(bits[mask0] < bits[mask1]) return solve0(mask0, mask1, maskq);
else return solve1(mask0, mask1, maskq);
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
cin >> n >> q;
cin >> Val;
precalc();
while(q--)
cout << query() << '\n';
return 0;
}
