281. [USACO Dec08] 密信

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.

贝茜是最想逃脱的奶牛之一！为此，奶牛们互相之间发送秘密的二进制信息。
作为一个聪明的反间谍人员，约翰截获了共M(1 <= M <= 50,000)条信息的前b_i (1 <= b_i <= 10,000) 位。
约翰汇编了一个长度为N (1 <= N <= 50,000)部分单词表，这是奶牛们常用的。不幸的是，他只知道单词j的前c_j (1 <= c_j <= 10,000)位。
对于每一个单词j，他想知道有多少个截取信息与单词相匹配（例如，对于单词j，有多少次信息与单词的初始字母相同）。
你的工作是计算这些数字。 输入的数位总数（例如，b_i 与 c_j的和）不超过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
输入格式:
第1行: 两个整数: M 和 N 
第2..M+1行: 行 i+1 用一个整数描述截取信息 i b_i 后面跟着b_i个用一个空格隔开的0和1
每M+2..M+N+1行: 行 M+j+1 用一个整数表示单词j c_j 后面跟着c_j个用一个空格隔开的0和1

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.
The intercepted messages start with 010, 1, 100, and 110.
The possible codewords start with 0, 1, 01, 01001, and 11.

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