19515번 - Jong Hyok and String 다국어

문제

Jong Hyok loves strings consisting of lowercase English letters. One day, he gave a problem to his friend, which happened to be... you! He wrote down $n$ strings $P_1,ドル $P_2,ドル $\ldots,ドル $P_n$ in front of you, and then asked $m$ questions.

Consider a string $S$. Define the $\mathit{StrangeSet} (S)$ as the set of all pairs $(i, j)$ such that $S$ occurs in $P_i$ as a substring ending at position $j$.

When asking question number $k,ドル Jong Hyok gives you a string $Q_k$. You must find the number of different strings $T$ such that $\mathit{StrangeSet} (Q_k) = \mathit{StrangeSet} (T)$ and $T$ is a substring of at least one of the given $n$ strings.

입력

The first line of input contains two integers $n$ and $m$ (1ドル \le n \le 10^5,ドル 1ドル \le m \le 5 \cdot 10^5$).

The next $n$ lines contain strings $P_1,ドル $P_2,ドル $\ldots,ドル $P_n,ドル one per line (1ドル \le |P_i| \le 10^5$).

The following $m$ lines contain strings $Q_1,ドル $Q_2,ドル $\ldots,ドル $Q_m,ドル one per line (1ドル \le |Q_k| \le 10^5$).

All $n + m$ strings consist of lowercase English letters.

The sum of all $|P_i|$ in the input does not exceed 10ドル^5$.

The sum of all $|P_i|$ and all $|Q_k|$ in the input is at most 2ドル \cdot 10^6$.

출력

For each question, print one integer on a separate line: the answer to this question.

제한

힌트