#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
int L, K;
short PreCalc[4096][6561];
vector<pair<int, int>> PreComp;
void recursion(int i, int mask1, int mask2, int value, int pw)
{
if (i == L - K)
{
for (int k = 0; k < (1 << (L - K)); k++)
if ((mask1 & k) == k && (mask2 & k) == mask2)
PreComp.push_back({value, k});
}
else
{
recursion(i + 1, mask1, mask2, value, pw * 3);
recursion(i + 1, mask1 | (1 << i), mask2 | (1 << i), value + pw, pw * 3);
recursion(i + 1, mask1 | (1 << i), mask2, value + 2 * pw, pw * 3);
}
}
void Yoshi()
{
int Q;
string s;
cin >> L >> Q >> s;
K = (L <= 13 ? 6 : 12);
if (L <= K)
{
while (Q--)
{
string t;
cin >> t;
reverse(t.begin(), t.end());
int mask1 = 0, mask2 = 0;
for (int i = 0; i < t.size(); i++)
{
if (t[i] == '?')
mask1 |= (1 << i);
else if (t[i] == '1')
mask1 |= (1 << i), mask2 |= (1 << i);
}
int r = 0;
for (int i = 0; i < (1 << L); i++)
if ((mask1 & i) == i && (mask2 & i) == mask2)
r += s[i] - '0';
cout << r << endl;
}
}
else
{
recursion(0, 0, 0, 0, 1);
for (int low = 0; low < (1 << K); low++)
{
int a[1 << (L - K)];
for (int i = 0; (i << K) < s.size(); i++)
a[i] = max(0, s[(i << K) + low] - '0');
for (auto &[x, y] : PreComp)
PreCalc[low][x] += a[y];
}
while (Q--)
{
string t;
cin >> t;
reverse(t.begin(), t.end());
int mask1 = 0, mask2 = 0;
for (int i = 0; i < K; i++)
{
if (t[i] == '?')
mask1 |= (1 << i);
else if (t[i] == '1')
mask1 |= (1 << i), mask2 |= (1 << i);
}
int pw = 1, g = 0;
for (int i = K; i < t.size(); i++)
{
if (t[i] == '1')
g += pw;
else if (t[i] == '?')
g += 2 * pw;
pw *= 3;
}
int r = 0;
for (int i = 0; i < (1 << K); i++)
if ((mask1 & i) == i && (mask2 & i) == mask2)
r += PreCalc[i][g];
cout << r << endl;
}
}
}
signed main()
{
#ifndef yoshi_likes_e4
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(problem ".inp", "r"))
{
freopen(problem ".inp", "r", stdin);
freopen(problem ".out", "w", stdout);
}
#endif
init();
int t = 1;
#if multitest
cin >> t;
#endif
while (t--)
Yoshi();
}
