#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] = {};
/*
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 < n)
{
if (qry[i] == '?') return qry1(i + 1, val << 1) + qry1(i + 1, (val << 1) ^ 1);
else return qry1(i + 1, (val << 1) ^ (qry[i] - '0'));
}
else {return s[val] - '0';}
}
int qry2(int t, int i, int val, bool c)
{
if (i < n)
{
if (qry[i] == '?') return qry2(t, i + 1, (val << 1) ^ t, c);
else if (qry[i] - '0' == t) return qry2(t, i + 1, (val << 1), c ^ t) + qry2(t, i + 1, (val << 1) ^ 1, c ^ (!t));
else return qry2(t, i + 1, (val << 1) ^ (qry[i] - '0'), c);
}
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) {cout << qry2(0, 0, 0, 0) << "\n";}
else if (mn == b) {cout << qry2(1, 0, 0, 0) << "\n";}
else {cout << qry1(0, 0) << "\n";}
}
return 0;
}
