#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(const T &v, int lim = 1e9)
{
for(auto x : v)
if(lim-- > 0) cout << x << " ";
cout << "\n";
}
int main()
{
ios::sync_with_stdio(0); cin.tie(NULL);
int n, q;
cin >> n >> q;
string s, t;
cin >> s;
int F0[(1 << n)];
int F1[(1 << n)];
for(int mask = 0; mask < (1 << n); mask++)
{
F0[mask] = s[mask] - '0';
F1[mask] = s[(1 << n) - mask - 1] - '0';
}
for(int i = 0; i < n; i++)
{
for(int mask = 0; mask < (1 << n); mask++)
{
if(mask & (1 << i))
{
F0[mask] += F0[mask ^ (1 << i)];
F1[mask] += F1[mask ^ (1 << i)];
}
}
}
while(q--)
{
cin >> t;
vector<int> e0, e1, e2;
int num = 0, num2 = 0;
for(int i = 0; i < t.size(); i++)
{
int exp = (1 << (t.size() - i - 1));
if(t[i] == '0') e0.push_back(exp);
else if(t[i] == '1') e1.push_back(exp), num2 += exp;
else
{
e2.push_back(exp);
num += exp;
}
}
// cout << "num: " << num << endl;
if(e0.size() <= 6)
{
int m = e0.size(), ans = 0;
// print(e0);
for(int mask = 0; mask < (1 << m); mask++)
{
int tmp = 0;
int p_cnt = 0;
for(int i = 0; i < m; i++)
{
if(mask & (1 << i))
{
tmp |= e0[i];
p_cnt++;
}
}
if(p_cnt & 1)
ans += F1[tmp | num];
else
ans -= F1[tmp | num];
}
cout << abs(ans) << '\n';
}
else if(e1.size() <= 6)
{
int m = e1.size(), ans = 0;
// print(e0);
for(int mask = 0; mask < (1 << m); mask++)
{
int tmp = 0;
int p_cnt = 0;
for(int i = 0; i < m; i++)
{
if(mask & (1 << i))
{
tmp |= e1[i];
p_cnt++;
}
}
if(p_cnt & 1)
ans += F0[tmp | num];
else
ans -= F0[tmp | num];
}
cout << abs(ans) << '\n';
}
else
{
int m = e2.size(), ans = 0;
// print(e0);
for(int mask = 0; mask < (1 << m); mask++)
{
int tmp = 0;
for(int i = 0; i < m; i++)
{
if(mask & (1 << i))
tmp |= e2[i];
}
ans += s[tmp | num2] - '0';
}
cout << ans << "\n";
}
}
}
