#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int a[(1<<17)+1];
vector <int> seg[(1<<18)+1];
void build(int id,int tl,int tr){
if (tl==tr){
seg[id].pb(a[tl]);
return;
}
int tm=(tl+tr)/2;
build(2*id,tl,tm);
build(2*id+1,tm+1,tr);
seg[id].pb(seg[2*id][0]+seg[2*id][1]);
}
void gol(int id,int oriid,int dep){
if (!dep){
seg[id].pb(seg[oriid].back());
return;
}
gol(2*id,2*oriid,dep-1);
gol(2*id+1,2*oriid+1,dep-1);
seg[id].pb(seg[2*id].back()+seg[2*id+1].back());
}
void gor(int id,int oriid,int dep){
if (!dep){
seg[id].back()+=seg[oriid].back();
return;
}
gor(2*id,2*oriid,dep-1);
gor(2*id+1,2*oriid+1,dep-1);
seg[id].back()=seg[2*id].back()+seg[2*id+1].back();
}
void rebuild(int id,int dep){
gol(id,2*id,dep-1);
gor(id,2*id+1,dep-1);
}
void unbuild(int id,int dep){
seg[id].pop_back();
if (dep<=1) return;
unbuild(2*id,dep-1);
unbuild(2*id+1,dep-1);
}
int N;
int ans[1000010];
pair <long long,int> want[1000010];
int idxwant;
void answer(){
build(1,1,(1<<N));
long long pw=1;
sort(want+1,want+idxwant+1);
stack <int> st;
for (int i=0; i<=N; i++) st.push(1<<i);
int f;
for (int i=1; i<=idxwant; i++){
f=N;
for (int j=0; j<2*N; j++){
if ((want[i-1].x&(1ll<<j))!=(want[i].x&(1ll<<j))) f=N-j/2-1;
}
for (int j=N-1; j>=f; j--){
st.pop();
if (want[i-1].x&(1ll<<((N-j)*2-1))) unbuild(st.top(),N-j);
}
for (int j=f; j<N; j++){
if (want[i].x&(1ll<<((N-j)*2-1))){
st.push(st.top());
rebuild(st.top(),N-j);
} else if (want[i].x&(1ll<<((N-j-1)*2))) st.push(st.top()*2+1);
else st.push(st.top()*2);
}
ans[want[i].y]+=seg[st.top()].back();
}
for (int i=1; i<(1<<(N-1)); i++) seg[i].clear();
}
pair <long long,int> qu[1000010];
void solve(){
int n,q;
cin>>n>>q;
int arr[(1<<n)+1];
for (int i=1; i<=(1<<n); i++){
char c; cin>>c;
arr[i]=(c-'0');
}
long long pw=1;
for (int i=1; i<=q; i++){
string str; cin>>str;
qu[i].x=0;
pw=1;
for (int j=n-1; j>=0; j--){
if (str[j]=='?') qu[i].x+=pw*2;
else if (str[j]=='1') qu[i].x+=pw;
pw*=4;
}
qu[i].y=i;
}
if (n<=17){
N=n;
for (int i=1; i<=(1<<n); i++) a[i]=arr[i];
for (int i=1; i<=q; i++) want[i]=qu[i];
idxwant=q;
answer();
} else {
N=17;
for (int mask=0; mask<8; mask++){
for (int i=1; i<=(1<<N); i++) a[i]=arr[8*(i-1)+mask+1];
idxwant=0;
for (int i=1; i<=q; i++){
int b0=(mask&1);
if (b0&&qu[i].x%4==0) continue;
if (!b0&&qu[i].x%4==1) continue;
int b1=(mask>>1)&1;
if (b1&&(qu[i].x>>2)%4==0) continue;
if (!b1&&(qu[i].x>>2)%4==1) continue;
int b2=(mask>>2)&1;
if (b2&&(qu[i].x>>4)%4==0) continue;
if (!b2&&(qu[i].x>>4)%4==1) continue;
want[++idxwant]={(qu[i].x>>6),qu[i].y};
}
answer();
}
}
for (int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t=1;
//cin>>t;
while (t--) solve();
}
