#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int L, T; cin >> L >> T;
int n = (1 << L);
int A[n];
for(int i = 0; i < n; ++i)
{
char c; cin >> c;
A[i] = c - '0';
}
int B[n]; for(int i = 0; i < n; ++i) B[i] = A[i];
for(int i = 0; i < L; ++i)
{
for(int j = 0; j < n; ++j)
if(j >> i & 1) B[j] += B[j ^ (1 << i)];
}
int C[n]; for(int i = 0; i < n; ++i) C[i] = A[i];
for(int i = 0; i < L; ++i)
{
for(int j = 0; j < n; ++j)
if(j >> i & 1) C[j ^ (1 << i)] += C[j];
}
// for(auto i : A) cout << i << ' '; cout << endl;
// for(auto i : B) cout << i << ' '; cout << endl;
// for(auto i : C) cout << i << ' '; cout << endl;
while(T--)
{
int a = 0, b = 0, c = 0;
int arr[L];
for(int i = L - 1; i >= 0; --i)
{
char t; cin >> t;
if(t == '0') arr[i] = 0, ++c;
else if(t == '1') arr[i] = 1, ++b;
else arr[i] = 2, ++a;
}
if(a <= b && a <= c)
{
int N = 1 << a;
vector<int> bt; int bs = 0;
for(int i = 0; i < L; ++i)
{
if(arr[i] == 2) bt.push_back(1 << i);
else if(arr[i] == 1) bs |= (1 << i);
}
int ans = A[bs];
for(int i = 1; i < N; ++i)
{
int t = __builtin_ctz(i);
for(int j = 0; j < t; ++j) bs ^= bt[j];
bs ^= bt[t];
ans += A[bs];
}
cout << ans << '\n';
}
else if(b <= a && b <= c)
{
int N = 1 << b;
vector<int> bt; int bs = 0;
for(int i = 0; i < L; ++i)
{
if(arr[i] == 1) bt.push_back(1 << i), bs |= (1 << i);
else if(arr[i] == 2) bs |= (1 << i);
}
long long ans = B[bs];
for(int i = 1; i < N; ++i)
{
int t = __builtin_ctz(i);
for(int j = 0; j < t; ++j) bs ^= bt[j];
bs ^= bt[t];
if(__builtin_parity(i)) ans -= B[bs];
else ans += B[bs];
}
cout << ans << '\n';
}
else
{
int N = 1 << c;
vector<int> bt; int bs = 0;
for(int i = 0; i < L; ++i)
{
if(arr[i] == 0) bt.push_back(1 << i);
else if(arr[i] == 1) bs |= (1 << i);
}
long long ans = C[bs];
for(int i = 1; i < N; ++i)
{
int t = __builtin_ctz(i);
for(int j = 0; j < t; ++j) bs ^= bt[j];
bs ^= bt[t];
if(__builtin_parity(i)) ans -= C[bs];
else ans += C[bs];
}
cout << ans << '\n';
}
}
}
