Bessie mène les vaches dans une tentative d'évasion ! Elles s'envoient des messages binaires secrets.

Le contre-espion toujours habile Farmer John intercepte les premiers $b_{i}$ bits, $(1 \le b_{i} \le 10,000)$, de chacun des $M$ messages, $(1 \le M \le 50,000)$.

Il liste $N$ mots de code partiels, $(1 \le N \le 50,000)$, qu'il pense utilisés par les vaches. Hélas, il ne connaît que les premiers $c_{j}$ bits du mot $j$, $(1 \le c_{j} \le 10,000)$.

Calculez pour chaque mot $j$ le nombre de messages interceptés compatibles, c'est-à-dire dont les bits initiaux sont les mêmes que ceux du mot.

Le total des bits saisis, somme des $b_{i}$ et $c_{j}$, ne dépasse pas $500,000$.

Entrée

• Ligne $1$ : entiers $M$, $N$.

• Lignes $2,\ldots,M+1$ : la ligne $i+1$ donne le message $i$ par l’entier $b_{i}$ puis $b_{i}$ valeurs 0 ou 1 séparées par des espaces.

• Lignes $M+2,\ldots,M+N+1$ : la ligne $M+j+1$ donne le mot $j$ par l’entier $c_{j}$ puis $c_{j}$ valeurs 0 ou 1 séparées par des espaces.

Sortie

• Lignes $1,\ldots,M$ : ligne $j$, nombre de messages compatibles avec le mot $j$.

Exemples

Entrée 1

4 5
3 0 1 0
1 1
3 1 0 0
3 1 1 0
1 0
1 1
2 0 1
5 0 1 0 0 1
2 1 1

Sortie 1

1
3
1
1
2

Remarque

Quatre messages, cinq mots. Débuts des messages : 010, 1, 100, 110 ; des mots : 0, 1, 01, 01001, 11.

0 correspond seulement à 010 : $1$. 1 à 1, 100, 110 : $3$. 01 seulement à 010 : $1$. 01001 à 010 : $1$. 11 à 1, 110 : $2$.

Auteurs du problème : David Benjamin et Jacob Steinhardt, 2008