/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#pragma ("reroll") */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ins insert
#define F first
#define S second
const int mod = 1e9 + 7,N = 5010,inf = 1e18;
int anss;
string s;
int n,q;
unordered_map<string,int>mp;
int bp(int a,int b){
if(b==0) return 1;
if(b%2==0){
int p = (bp(a,b/2));
return (p * p) % mod;
}
else return (a * bp(a,b-1)) % mod;
}
int pw[21];
void rec(string t,int pos,int ans){
if(pos==t.size()){
anss+= s[ans] - '0';
return;
}
if(t[pos]=='1') {ans+=(1 << (n-pos-1));rec(t,pos+1,ans);return;}
else if(t[pos]=='0') {rec(t,pos+1,ans);return;}
rec(t,pos+1,ans);
rec(t,pos+1,ans+(1<<(n-pos-1)));
}
signed main(){
//freopen("snnfsn.in","r",stdin)
//freopen("snnfsn.out","w",stdout)
std::ios::sync_with_stdio(false);
cin.tie(0);
pw[0] = 1;
for(int i = 1;i<=20;i++){
pw[i] = (pw[i-1] * 29) % mod;
}
cin >> n >> q;
cin >> s;
while(q--){
string t;
cin >> t;
if(mp[t]!=0) anss = mp[t];
else rec(t,0,0);
cout << anss << '\n';
mp[t] = anss;
anss = 0;
}
}
