## [USACO Dec08]密信

 成绩 0 开启时间 2013年01月22日 星期二 14:35 折扣 0.8 折扣时间 2013年01月22日 星期二 14:35 允许迟交 是 关闭时间 2013年01月22日 星期二 14:35 输入文件 sec.in 输出文件 sec.out
Secret Message [David Benjamin and Jacob Steinhardt, 2008]

Bessie is leading the cows in an attempt to escape! To do this, the
cows are sending secret binary messages to each other.

Ever the clever counterspy, Farmer John has intercepted the first
b_i (1 <= b_i <= 10,000) bits of each of M (1 <= M <= 50,000) of
these secret binary messages.

He has compiled a list of N (1 <= N <= 50,000) partial codewords
that he thinks the cows are using. Sadly, he only knows the first
c_j (1 <= c_j <= 10,000) bits of codeword j.

For each codeword j, he wants to know how many of the intercepted
messages match that codeword (i.e., for codeword j, how many times
does a message and the codeword have the same initial bits).  Your
job is to compute this number.

The total number of bits in the input (i.e., the sum of the b_i and
the c_j) will not exceed 500,000.

Memory Limit: 32MB

POINTS: 270

PROBLEM NAME: sec

INPUT FORMAT:

* Line 1: Two integers: M and N

* Lines 2..M+1: Line i+1 describes intercepted code i with an integer
b_i followed by b_i space-separated 0's and 1's

* Lines M+2..M+N+1: Line M+j+1 describes codeword j with an integer
c_j followed by c_j space-separated 0's and 1's

SAMPLE INPUT (file sec.in):

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

INPUT DETAILS:

Four messages; five codewords.

OUTPUT FORMAT:

* Lines 1..N: Line j: The number of messages that the jth codeword
could match.

SAMPLE OUTPUT (file sec.out):

1
3
1
1
2

OUTPUT DETAILS:

0 matches only 010: 1 match
1 matches 1, 100, and 110: 3 matches
01 matches only 010: 1 match
01001 matches 010: 1 match
11 matches 1 and 110: 2 matches