题目描述

贝茜正在领导奶牛们逃跑。为了联络，奶牛们互相发送秘密信息。

信息是二进制的，共有 $m$ 条。反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 $i$ 条二进制信息的前 $b_i$ 位。他同时知道，奶牛使用 $n$ 条密码。但是，他仅仅了解第 $j$ 条密码的前 $c_j$ 位。

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

输入格式

• 第一行: 两个数：$n,m$
• 接下来 $n$ 行：每行先输入一个整数表示信息的长度，之后输入这个信息。所有数字之间都用空格隔开。
• 接下来 $m$ 行：每行先输入一个整数表示密码的长度，之后输入这个密码。所有数字之间都用空格隔开。

输出格式

共 $m$ 行，每行分别输出每条密码的匹配信息数。

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

数据规模与约定

对于 $100\%$ 的数据，$1\le m \le 50000$,$1\le n \le 50000$,$1 \le b_i \le 10000$,$1\le c_j \le 10000$。

在输入文件中，位的总数（即$\sum^{n}_{i=1} b_i+ \sum^{n}_{i=1} c_i$）不会超过 $5\times 10^5$。

提示

输入提示

共有 $4$ 条信息，$5$ 条密码。

被截获的信息以 $010$,$1$,$100$ 和 $110$ 开头。

可能的密码以 $0$,$1$,$01$,$01001$ 和 $11$ 开头。

输出提示

$0$ 仅和 $010$ 匹配，共匹配 $1$ 次；$1$ 和 $1$,$100$ 和 $110$ 匹配，共匹配 $3$ 次；$01$ 仅和 $010$ 匹配，共匹配 $1$ 次；$01001$ 仅和 $010$ 匹配，共匹配 $1$ 次；$11$ 和 $1$ 和 $110$ 匹配，共匹配 $2$ 次。

题目来源

Usaco 2008 Dec Gold