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.