#include <iostream>
#include <utility>
#include <tuple>
using namespace std;
const int SZ = 1 << 20;
int n, q, k;
string s;
string qry;
int dp[2][2][SZ] = {};
int cr[8], sz = 0;
/*
We can decompose a query into three types,
min(0, 1, ?) == 0, min(0, 1, ?) == 1, min(0, 1, ?) == ?
Then, we could find an algorithm that runs in 2^k for each possible type
Since k is at most 6, 2^k is at most 64, therefore 2^k * Q still works.
*/
int qry1(int i, int val)
{
if (i < sz) {return qry1(i + 1, val) + qry1(i + 1, val ^ cr[i]);}
else {return s[val] - '0';}
}
int qry2(int t, int i, int val, bool c)
{
if (i < sz) {return qry2(t, i + 1, val, c ^ t) + qry2(t, i + 1, val ^ cr[i], c ^ (!t));}
else
{
if (c) return -dp[t][n & 1][val];
else return dp[t][n & 1][val];
}
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
cin >> s;
k = s.size();
for (int i = 0; i < k; i++) {dp[0][0][i] = dp[1][0][i] = s[i] - '0';}
for (int i = 1; i <= n; i++)
{
int cri = i & 1, pv = !cri, msk = 1 << (i - 1);
for (int j = 0; j < k; j++)
{
for (int k = 0; k < 2; k++)
{
dp[k][cri][j] = dp[k][pv][j];
if (((j & msk) > 0) ^ !k) dp[k][cri][j] += dp[k][pv][j ^ msk];
}
}
}
for (int i = 0; i < q; i++)
{
cin >> qry;
int a = 0, b = 0, c = 0, mn;
for (int j = 0; j < n; j++)
{
a += (qry[j] == '0');
b += (qry[j] == '1');
c += (qry[j] == '?');
}
mn = min(a, min(b, c));
if (mn == a)
{
int val = 0;
for (int j = 0; j < n; j++)
{
if (qry[j] == '0') cr[sz++] = 1 << (n - 1 - j);
else if (qry[j] == '1') val ^= 1 << (n - 1 - j);
}
cout << qry2(0, 0, val, 0) << "\n";
}
else if (mn == b)
{
int val = 0;
for (int j = 0; j < n; j++)
{
if (qry[j] == '1') cr[sz++] = 1 << (n - 1 - j);
else if (qry[j] == '?') val ^= 1 << (n - 1 - j);
}
cout << qry2(1, 0, val, 0) << "\n";
}
else
{
int val = 0;
for (int j = 0; j < n; j++)
{
if (qry[j] == '?') cr[sz++] = 1 << (n - 1 - j);
else if (qry[j] == '1') val ^= 1 << (n - 1 - j);
}
cout << qry1(0, val) << "\n";
}
sz = 0;
}
return 0;
}
