Bessie prowadzi krowy w próbie ucieczki! Przesyłają sobie tajne wiadomości binarne.

Zawsze sprytny kontrwywiadowca Farmer John przechwycił pierwsze $b_{i}$ bitów, $(1 \le b_{i} \le 10,000)$, każdej z $M$ wiadomości, $(1 \le M \le 50,000)$.

Spisał $N$ częściowych słów kodowych, $(1 \le N \le 50,000)$, których zapewne używają krowy. Niestety zna tylko pierwsze $c_{j}$ bitów słowa $j$, $(1 \le c_{j} \le 10,000)$.

Dla każdego słowa $j$ policz zgodne przechwycone wiadomości, czyli mające takie same początkowe bity jak słowo.

Suma bitów wejścia, czyli suma $b_{i}$ i $c_{j}$, nie przekroczy $500,000$.

Wejście

• Wiersz $1$: całkowite $M$, $N$.

• Wiersze $2,\ldots,M+1$: wiersz $i+1$ opisuje wiadomość $i$ całkowitym $b_{i}$, potem $b_{i}$ wartości 0 lub 1 przez spacje.

• Wiersze $M+2,\ldots,M+N+1$: wiersz $M+j+1$ opisuje słowo $j$ całkowitym $c_{j}$, potem $c_{j}$ wartości 0 lub 1 przez spacje.

Wyjście

• Wiersze $1,\ldots,M$: wiersz $j$ — liczba wiadomości zgodnych ze słowem $j$.

Przykład

Wejście 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

Wyjście 1

1
3
1
1
2

Uwagi

Cztery wiadomości, pięć słów. Początki wiadomości: 010, 1, 100, 110; słów: 0, 1, 01, 01001, 11.

0 pasuje tylko do 010: $1$. 1 do 1, 100, 110: $3$. 01 tylko do 010: $1$. 01001 do 010: $1$. 11 do 1, 110: $2$.

Autorzy zadania: David Benjamin i Jacob Steinhardt, 2008