[Usaco2008 Dec]Secret Message 秘密信息

贝茜正在带领奶牛们逃跑。为了保持联络，奶牛们会互相发送由二进制位组成的秘密信息，共有 $N$ 条。反间谍能力很强的约翰截获了部分内容，并知道第 $i$ 条信息的前 $b_i$ 位。

约翰还知道奶牛们使用了 $M$ 条密码，但他只掌握了第 $j$ 条密码的前 $c_j$ 位。对于每条密码，他想知道有多少条截获的信息能够与之匹配。

若一条信息与一条密码在前 $\min(b_i,c_j)$ 位上完全相同，则称它们匹配。换言之，两者中较短的二进制串必须是较长二进制串的前缀。

输入格式

第一行输入两个整数 $N$ 和 $M$。

接下来 $N$ 行描述截获的信息。每行首先输入一个整数 $b_i$，表示该信息的长度，随后输入 $b_i$ 个二进制位。

再接下来 $M$ 行描述密码。每行首先输入一个整数 $c_j$，表示该密码的长度，随后输入 $c_j$ 个二进制位。

同一行中的所有整数均以空格分隔。

输出格式

输出共 $M$ 行。第 $j$ 行输出能够与第 $j$ 条密码匹配的信息数量。

样例输入

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

样例解释

• 密码 $0$ 只与信息 $010$ 匹配，共 $1$ 条；
• 密码 $1$ 与信息 $1$、$100$ 和 $110$ 匹配，共 $3$ 条；
• 密码 $01$ 只与信息 $010$ 匹配，共 $1$ 条；
• 密码 $01001$ 只与信息 $010$ 匹配，共 $1$ 条；
• 密码 $11$ 与信息 $1$ 和 $110$ 匹配，共 $2$ 条。

数据范围

• $1\le N\le 5\times 10^4$；
• $1\le M\le 5\times 10^4$；
• $1\le b_i\le 10^4$；
• $1\le c_j\le 10^4$；
• 输入中所有信息和密码的二进制位总数满足 $\sum b_i+\sum c_j\le 5\times 10^5$。

来源与许可

本题为 USACO 2008 December 试题「Secret Message 秘密信息」，题面与测试数据整理自 BZOJ。

样例 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
3
1
1
2