You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Original source: USACO 2008 Dec. Gold

Bessie is leading the cows in an escape. To communicate, the cows send secret messages to each other.

The messages are binary and consist of $M$ entries. John, who has strong anti-spying capabilities, has partially intercepted these messages and knows the first $b_i$ bits of the $i$-th binary message. He also knows that the cows use $N$ passwords. However, he only knows the first $c_j$ bits of the $j$-th password.

For each password $j$, he wants to know how many intercepted messages can match it. That is, how many messages share the same prefix with this password. Of course, the length of this prefix must be equal to the smaller of the password length and the message length.

Input Format

The first line contains $N$ and $M$, followed by $N$ lines describing the secret messages and then $M$ lines describing the passwords. Each line starts with an integer indicating the length of the message or password, followed by the message or password itself.

All numbers are separated by spaces.

Output Format

Output $M$ lines, each indicating the number of matching messages for the corresponding password.

Sample 1

$4$ messages and $5$ passwords.

The intercepted message prefixes are $010, 1, 100, 110$, and the possible password prefixes are $0, 1, 01, 01001, 11$.

$0$ only matches $010$;

$1$ matches $1, 100, 110$;

$01$ only matches $010$;

$01001$ matches $010$;

$11$ matches $1,110$.

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

1
3
1
1
2

Data Range and Hints

For $100\%$ of the data, $1\le M\le 50000,1\le N\le 50000,1\le b_i\le 10000,1\le c_j\le 10000$. The total number of bits, i.e., $\sum B_i+\sum C_i$, does not exceed $500000$.