#include<bits/stdc++.h>
using namespace std;
int dp1[1<<20],dp2[1<<20],orig[1<<20];
void readst(string &str){
char c=getchar();
while(c==' '||c=='\n')
c=getchar();
while(c!=' '&&c!='\n')
str+=c,c=getchar();
}
void brute(string a){
vector<int>can;
int k=0,l=a.size()-1,ans=0;
for(int i=0;i<=l;i++)
if(a[i]=='?') k<<=1,
can.push_back(l-i);
else k<<=1,k+=a[i]-48;
int x=can.size();
for(int i=0;i<1<<x;i++){
int k2=k;
for(int j=0;j<x;j++)
k2|=(i>>j&1)<<can[j];
ans+=orig[k2];
}
cout<<ans<<'\n';
}
void subs(string a){
vector<int>can;
int k=0,l=a.size()-1,ans=0;
for(int i=0;i<=l;i++)
if(a[i]=='?') k=k<<1|1;
else if(a[i]=='0') k<<=1;
else can.push_back(l-i),k=k<<1|1;
int x=can.size();
for(int i=0;i<1<<x;i++){
int k2=k;
for(int j=0;j<x;j++)
k2^=(i>>j&1)<<can[j];
int y=__builtin_popcount(i)%2;
ans+=(-y*2+1)*dp1[k2];
}
cout<<ans<<'\n';
}
void sups(string a){
vector<int>can;
int k=0,l=a.size()-1,ans=0;
for(int i=0;i<=l;i++)
if(a[i]=='?') k<<=1;
else if(a[i]=='1')k=k<<1|1;
else can.push_back(l-i),k<<=1;
int x=can.size();
for(int i=0;i<1<<x;i++){
int k2=k;
for(int j=0;j<x;j++)
k2^=(i>>j&1)<<can[j];
int y=__builtin_popcount(i)%2;
ans+=(-y*2+1)*dp2[k2];
}
cout<<ans<<'\n';
}
int main(){
int n,m;
string str;
cin>>n>>m;
readst(str);
for(int i=0;i<1<<n;i++)
dp1[i]=dp2[i]=orig[i]=str[i]-48;
for(int i=0;i<n;i++) for(int j=0;j<1<<n;j++)
if(j&1<<i) dp1[j]+=dp1[j^1<<i],dp2[j^1<<i]+=dp2[j];
while(m--){
string qr;
readst(qr);
int a=0,b=0,c=0;
for(auto i:qr)
if(i=='0')
a++;
else if(i=='1')
b++;
else c++;
if(c<=6)brute(qr);
else if(b<=6)subs(qr);
else sups(qr);
}
}
