#include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define forn(i,a,b) for(int i = a; i<b; i++) #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define mset(a,v) memset(a,v,sizeof(a)) #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const int MAXL = 21; const int MAXP = (1<<20); ll dp1[MAXP]; ll dp2[MAXP]; ll cost[MAXP]; ll L,Q; string s; vector<ll> one; vector<ll> zero; vector<ll> qsy; ll res = 0; ll bina; ll newbina; ll cnt; void f1(){ // mascara padre for(int y = L; y>=0; y--){ for(int x=(1<<L)-1; x>=0; x--){ if(y==L) dp1[x]+=cost[x]; else dp1[x]=dp1[x]+dp1[x|(1<<y)]; } } } void f2(){ // mascara hijo for(int y = L; y>=0; y--){ forn(x,0,1<<L){ if(y==L) dp2[x]+=cost[x]; else dp2[x]=dp2[x]+(x&(1<<y)? dp2[x^(1<<y)] :0); } } } int main(){ FIN; cin>>L>>Q; cin>>s; forn(i,0,1<<L){ dp1[i]=dp2[i]=0; cost[i]=s[i]-'0'; } f1(); f2(); vector<string> q(Q); forn(i,0,Q) cin>>q[i]; forn(i,0,Q){ one.clear(); zero.clear(); qsy.clear(); bina = 0; forn(j,0,SZ(q[i])){ if(q[i][j]=='0') zero.pb(j); if(q[i][j]=='1') one.pb(j),bina|=(1<<((L-1)-j)); if(q[i][j]=='?') qsy.pb(j); } res = 0; //cout<<"--------------------\n"; if(SZ(qsy)<=6){ forn(h,0,1<<SZ(qsy)){ newbina = bina; forn(k,0,SZ(qsy)) if(h&(1<<k)){ newbina|=(1<<((L-1)-qsy[k])); } if(cost[newbina]!=-1) res+=cost[newbina]; } }else if(SZ(one)<=6){ forn(h,0,SZ(qsy)) bina|=(1<<((L-1)-qsy[h])); res=dp2[bina];//f2(bina,0); //cout<<res<<" "; for(int h = L-1; h>=0; h--) cout<<(bina&(1<<h)?1:0); cout<<'\n'; forn(h,1,1<<SZ(one)){ cnt = 0; newbina = bina; forn(k,0,SZ(one)) if(h&(1<<k)){ newbina^=(1<<((L-1)-one[k])); cnt++; } if(cnt%2==0) res+=dp2[bina];//f2(newbina,0); else res-=dp2[bina];//f2(newbina,0); } }else{ res=dp1[bina]; //cout<<res<<" "<<bina<<'\n'; forn(h,1,1<<SZ(zero)){ cnt = 0; newbina = bina; forn(k,0,SZ(zero)) if(h&(1<<k)){ newbina^=(1<<((L-1)-zero[k])); cnt++; } if(cnt%2==0) res+=dp1[newbina];//f1(newbina,0); else res-=dp1[newbina];//f1(newbina,0); } } cout<<res<<'\n'; } return 0; }