Habilidades especiais

A Maratona de Programação WEB é uma competição organizada pela Sociedade Brasileira de CSS (SBC). Nela, as equipes são formadas por exatamente três integrantes, e o objetivo principal é desenvolver um projeto utilizando CSS e JavaScript.

Cada competidor possui um subconjunto das $K$ habilidades mais importantes de um desenvolvedor frontend. Alguns exemplos dessas habilidades são:

1. Centralizar uma div (o clássico ritual do front);
2. Dominar o CSS sem perder a sanidade;
3. Lembrar a diferença entre == e ===;
4. Invocar o poder místico de um console.log().

Uma universidade possui $N$ alunos, e cada aluno domina um subconjunto das $K$ habilidades. A habilidade total de uma equipe é definida pela união dos subconjuntos de seus integrantes.

Por exemplo, considere as habilidades de três alunos:

$$ membro_1 = [1, 2]\space\space membro_2 = [2]\space\space membro_3 = [1, 4] $$

Assim, a equipe formada por esses três alunos possui como conjunto de habilidades ${1, 2, 4}$.

O professor Joãozinho, utilizando uma LLM muito avançada, descobriu $M$ subconjuntos de habilidades especiais. Se o conjunto de habilidades de uma equipe for exatamente igual a um desses subconjuntos especiais, então ela tem grande chance de se tornar campeã.

Agora, o professor deseja saber, para cada subconjunto especial, quantas equipes distintas, formadas por três alunos, podem ser montadas de modo que o conjunto resultante de habilidades seja exatamente aquele subconjunto.

A primeira linha contém dois inteiros $N$ e $K$ ($1 \leq N \leq 10^5$, $1 \leq K \leq 20$), representando, respectivamente, o número de alunos e o total de habilidades possíveis.

As próximas $N$ linhas contêm uma string binária $H_i$ de tamanho $K$, que representa o conjunto de habilidades do aluno $i$. Se o caractere na posição $j$ ($1 \leq j \leq K$) for 1, significa que o aluno possui a habilidade $j$; caso contrário, ele não a possui.

A próxima linha contém um inteiro $M$ ($1 \leq M \leq 5 \cdot 10^4$), representando o número de subconjuntos especiais.

As próximas $M$ linhas contêm uma string binária $E_i$ de tamanho $K$, que representa um subconjunto especial. Se o caractere na posição $j$ ($1 \leq j \leq K$) for 1, significa que o subconjunto especial inclui a habilidade $j$; caso contrário, não inclui.

A saída deve conter $M$ linhas. A $i$-ésima linha deve conter um único inteiro representando a quantidade de equipes distintas, formadas por três alunos, cujo conjunto de habilidades seja exatamente igual a $E_i$.