P2922 [USACO08DEC] Secret Message G

题目描述

贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息． 信息是二进制的，共有 $M$（$1 \le M \le 50000$）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 $i$ 条二进制信息的前 $b_i$（$1 \le b_i \le 10000$）位，他同时知道，奶牛使用 $N$（$1 \le N \le 50000$）条暗号．但是，他仅仅知道第 $j$ 条暗号的前 $c_j$（$1 \le c_j \le 10000$）位。

对于每条暗号 $j$，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中，位的总数（即 $\sum b_i + \sum c_i$）不会超过 $500000$。

输入格式

第一行输入两个整数$M$ and $N$。 之后 M 行描述信息，每行先输入一个整数表示信息的长度，之后输入这个信息。 之后 N 行描述密码，每行先输入一个整数表示密码的长度，之后输入这个密码。 所有数字之间都用空格隔开。

输出格式

共 N 行，输出每条密码的匹配信息数。

输入输出样例 #1

输入 #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

输出 #1

1 
3 
1 
1 
2

说明/提示

4 条信息，5 条密码

信息前缀是 010, 1, 100, 110，

密码前缀是 0, 1, 01, 01001, 11。

0 只配对 010；

1 配对 1, 100, 110；

01 只配对 010；

01001 配对 010；

11 配对 1,110。

数据范围与提示

对于 $100\%$ 的数据， $1\le M\le 50000,1\le N\le 50000,1\le b_i\le 10000,1\le c_j\le 10000$，位的总数即 $\sum B_i+\sum C_i$ 不会超过 500000。