Bessie guida le mucche in un tentativo di fuga! Si inviano messaggi binari segreti.

La controspia sempre abile Farmer John intercetta i primi $b_{i}$ bit, $(1 \le b_{i} \le 10,000)$, di ciascuno dei $M$ messaggi, $(1 \le M \le 50,000)$.

Elenca $N$ parole di codice parziali, $(1 \le N \le 50,000)$, che pensa usate dalle mucche. Purtroppo conosce solo i primi $c_{j}$ bit della parola $j$, $(1 \le c_{j} \le 10,000)$.

Calcola per ogni parola $j$ quanti messaggi intercettati corrispondono, cioè hanno gli stessi bit iniziali della parola.

Il totale di bit in input, somma di $b_{i}$ e $c_{j}$, non supera $500,000$.

Input

• Riga $1$: interi $M$, $N$.

• Righe $2,\ldots,M+1$: riga $i+1$, messaggio $i$ con intero $b_{i}$ seguito da $b_{i}$ valori 0 o 1 separati da spazi.

• Righe $M+2,\ldots,M+N+1$: riga $M+j+1$, parola $j$ con intero $c_{j}$ seguito da $c_{j}$ valori 0 o 1 separati da spazi.

Output

• Righe $1,\ldots,M$: riga $j$, numero di messaggi che corrispondono alla parola $j$.

Esempi

Input 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

Output 1

1
3
1
1
2

Nota

Quattro messaggi, cinque parole. Inizi: messaggi 010, 1, 100, 110; parole 0, 1, 01, 01001, 11.

0 corrisponde solo a 010: $1$. 1 a 1, 100, 110: $3$. 01 solo a 010: $1$. 01001 a 010: $1$. 11 a 1, 110: $2$.

Autori del problema: David Benjamin e Jacob Steinhardt, 2008