#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1600005
using namespace std;
int n, m, a[N], dp[N], prec[N], cvp[N], kaps[3000][200];
char c;
pair < int , int > q[N];
void hesapla(int);
// bas bitinin ikilik bitde 7 uzunlugunda ? isaretsiz oldugunu varsay bit 13 uzun.
int f(int bas, int bit){
if(dp[bit] != -1)
return dp[bit];
int x = prec[bit];
if(x <= 0){
x = -x;
// cout << x << endl;
int sorg = bas*(1<<13) + x;
// cout << sorg<< " -> " << a[sorg] << endl;
return dp[bit] = a[sorg];
}
return dp[bit] = f(bas, bit - x) + f(bas, bit - x - x);
}
//bu sefer bas'da soru isareti olabilir.
int bul(int bas, int son){
int x = prec[bas];
if(x <= 0)
return f(-prec[bas] , son);
return bul(bas - x, son) + bul(bas - x - x, son);
}
bool kapsar(int uc, int iki){
// cout << uc << " " << iki << endl;
if(kaps[uc][iki] != -1)
return kaps[uc][iki];
int yuc = uc;
int yiki = iki;
for(int i = 1; i <= 7; i++){
if(yuc%3 != 2 and yiki%2 != yuc%3)
return kaps[uc][iki] = 0;
yuc /= 3;
yiki /= 3;
}
return kaps[uc][iki] = 1;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
for(int i = 0; i < N; i++)
hesapla(i);
memset(dp, -1, sizeof dp);
memset(kaps, -1, sizeof kaps);
scanf("%d %d",&n ,&m);
for(int i = 0; i < (1<<n); i++){
scanf(" %c",&c);
a[i] = c - '0';
}
for(int i = 1; i <= m; i++){
int bit = 0, say = 0, son = 0, crp = 1;
for(int i = 1; i <= n; i++){
scanf(" %c" ,&c);
bit *= 3;
bit += (c == '?') ? 2 : c - '0';
}
// cout << bit << endl;
for(int say = 1; say <= 13; say++){
son += crp*(bit%3);
crp *= 3;
bit/=3;
}
// cout << bit << " -> " << son << endl;
q[i] = mp(bit, son);
// printf("%d\n",bul(bit, son));
}
for(int i = 0; i < (1<<7); i++){
memset(dp, -1, sizeof dp);
for(int j = 1; j <= m; j++)
if(kapsar(q[j].st, i)){
// cout << i << " - > " << q[j].nd << endl;
cvp[j] += bul(i, q[j].nd);
}
}
for(int i = 1; i <= m; i++)
printf("%d\n",cvp[i]);
return 0;
}
void hesapla(int bit){
int yed = bit, crp = 1, ckr = -1;
while(yed){
if(yed%3 == 2){
ckr = crp;
break;
}
crp *= 3;
yed /= 3;
}
prec[bit] = ckr;
if(ckr == -1){
yed = bit;
int say = 0, cvp = 0;
while(yed){
cvp += (1<<say)*(yed%3);
say++;
yed /= 3;
}
prec[bit] = -cvp;
}
}
