题目描述

给定 $N$ 个字符串 $S_1, S_2, \dots, S_N$，接下来进行 $M$ 次询问，每次询问给定一个字符串 $T$，求 $S_1 \sim S_N$ 中有多少个字符串是 $T$ 的前缀。

输入字符串的总长度不超过 $10^6$，仅包含小写字母。

输入格式

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

接下来 $N$ 行每行输入一个字符串 $S_i$。

接下来 $M$ 行每行一个字符串 $T$ 用以询问。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

样例

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0

样例解释

$S$ 集合：ab, bc, abc

询问1：abc
前缀有：a, ab, abc
$S$ 中匹配的有 ab 和 abc，共 2 个，输出 2。

询问2：efg
前缀没有与 $S$ 中匹配的，输出 0。

数据范围

• $1 \le N, M \le 10^5$
• 输入字符串总长度不超过 $10^6$

时空限制

• 时间限制：1 秒
• 空间限制：256 MB