Problem Description

Given $N$ strings $S_1,S_2,\cdots,S_N$, you will then make $M$ queries. In each query, a string $T$ is given. Find how many strings among $S_1 \sim S_N$ are prefixes of $T$.

The total length of all input strings does not exceed $10^6$, and they contain only lowercase letters.

Input Format

The first line contains two integers $N,M$.

The next $N$ lines each contain a string $S_i$.

The next $M$ lines each contain a string $T$ for querying.

Output Format

For each query, output an integer representing the answer.

Each answer occupies one line.

3 2
ab
bc
abc
abc
efg

2
0

Hint

Constraints: $1 \le N,M \le 10^5$.

Translated by ChatGPT 5