#include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> using namespace std; namespace mine { typedef long long ll; #define pr pair<int, int> #define FR first #define SE second #define vc vector #define bin(x) (1ll << (x)) #define fo(i, a, b) for (register int i = (a); i <= (b); i++) #define fd(i, a, b) for (register int i = (a); i >= (b); i--) ll qread() { ll ans = 0, f = 1; char c = getchar(); while (c < '0' or c > '9') { if (c == '-') f = -1; c = getchar(); } while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar(); return ans * f; } void write(int num) { if (num < 0) putchar('-'), num = -num; if (num >= 10) write(num / 10); putchar('0' + num % 10); } void write1(int num) { write(num); putchar(' '); } void write2(int num) { write(num); putchar('\n'); } const int MOD = 998244353; int mm(int x) { return x < MOD ? x : x - MOD; } void add(int &x, const int y) { x = mm(x + y); } const int N = 21, M = bin(20) + 10; int val[M], down[M], up[M], siz[M]; char qes[N], str[M]; void main() { int n = qread(), q = qread(), m = bin(n); scanf("%s", str); fo(i, 0, m - 1) val[i] = str[i] - '0'; memcpy(down, val, sizeof val); memcpy(up, val, sizeof val); fo(pos, 0, n - 1) fo(s, 0, m - 1) if (s & bin(pos)) down[s] += down[s ^ bin(pos)]; fo(pos, 0, n - 1) fo(s, 0, m - 1) if (s & bin(pos)) up[s ^ bin(pos)] += up[s]; fo(s, 1, m - 1) siz[s] = siz[s >> 1] + (s & 1); fo(s, 0, m - 1) if (siz[s] & 1) siz[s] = -1; else siz[s] = 1; while (q--) { scanf("%s", qes); reverse(qes, qes + n); int c0 = 0, c1 = 0, c2 = 0; fo(i, 0, n - 1) if (qes[i] == '0') c0++; else if (qes[i] == '1') c1++; else c2++; if (c2 <= c0 and c2 <= c1) //? { int mask1 = 0, mask2 = 0; fo(i, 0, n - 1) if (qes[i] == '?') mask1 |= bin(i); else mask2 ^= bin(i) * (qes[i] - '0'); int ans = val[mask2]; for (int now = mask1; now > 0; now = (now - 1) & mask1) ans += val[mask2 | now]; write2(ans); } else if (c1 <= c0 and c1 <= c2) // 1 { int mask1 = 0, mask2 = 0; fo(i, 0, n - 1) if (qes[i] == '1') mask1 |= bin(i); else if (qes[i] == '?') mask2 |= bin(i); int ans = down[mask2] * siz[mask1]; for (int now = mask1; now > 0; now = (now - 1) & mask1) ans += down[mask2 | now] * siz[mask1 ^ now]; write2(abs(ans)); } else // 0 { int mask1 = 0, mask2 = 0; fo(i, 0, n - 1) if (qes[i] == '0') mask1 |= bin(i); else if (qes[i] == '1') mask2 |= bin(i); int ans = up[mask2] * siz[mask1]; for (int now = mask1; now > 0; now = (now - 1) & mask1) ans += up[mask2 | now] * siz[mask1 ^ now]; write2(abs(ans)); } } } }; // namespace mine int main() { // freopen("z.txt","r",stdin); srand(time(0)); mine::main(); }