Secret Message

Bessie is leading the cows in an attempt to escape, and to coordinate they send each other secret binary (0 and 1) messages.

A counterspy has intercepted the first $b_i$ ($1 \le b_i \le 10^4$) bits of each of $M$ ($1 \le M \le 5 \times 10^4$) secret binary messages.

He has also compiled a list of $N$ ($1 \le N \le 5 \times 10^4$) partial codewords that he believes the cows are using. For codeword $j$ he only knows its first $c_j$ ($1 \le c_j \le 10^4$) bits.

A message and a codeword match when one is a prefix of the other: reading from the first bit, they agree on every bit up to the length of the shorter of the two. For each codeword $j$, determine how many of the $M$ intercepted messages match it.

The total number of bits in the input (the sum of all $b_i$ and all $c_j$) does not exceed $5 \times 10^5$.

• Line 1: two integers $M$ and $N$.
• Lines 2 to $M+1$: line $i+1$ describes intercepted message $i$ as an integer $b_i$ followed by $b_i$ space-separated bits (each $0$ or $1$).
• Lines $M+2$ to $M+N+1$: line $M+j+1$ describes codeword $j$ as an integer $c_j$ followed by $c_j$ space-separated bits (each $0$ or $1$).

• Lines 1 to $N$: line $j$ contains a single integer, the number of intercepted messages that match codeword $j$.

Consider the four messages $010$, $1$, $100$, $110$ and the five codewords $0$, $1$, $01$, $01001$, $11$.

• Codeword $0$ matches only $010$: $1$ match.
• Codeword $1$ matches $1$, $100$, and $110$: $3$ matches.
• Codeword $01$ matches only $010$: $1$ match.
• Codeword $01001$ matches only $010$ (the message $010$ is a prefix of it): $1$ match.
• Codeword $11$ matches $1$ and $110$: $2$ matches.