Background

Time flies. That afternoon about “homophone replacement” is still clearly imprinted in little $\omega$'s mind.

Back then, he insisted on exact matching: only completely identical substrings could be replaced. However, reality often did not go as hoped, and even tiny differences were enough to ruin all efforts.

Many years later, when little $\omega$ opened his linguistics notes again, he gained a new understanding of “homophones”: why demand complete equality? Having the same beginning or the same ending is already “homophonic” enough. Just like bits of memory, it does not need to be fully replayed; only a beginning or an ending is enough to connect the whole story.

Problem Description

Little $\omega$ is an algorithm contest participant who likes linguistics. In linguistics, homophone replacement means replacing original words with words that have the same or similar pronunciation. Little $\omega$ found that the process of homophone replacement can be described using prefix or suffix relationships of strings. Specifically, little $\omega$ defines homophone replacement as the following string problem:

• String $X$ is a homophone replacement of $Y$ if and only if $X$ is a prefix of $Y$, or $X$ is a suffix of $Y$.
• Let the language set be $S = \{S_1, S_2, \dots, S_n\}$. A homophone triple of string $T$ means splitting $T$ into three non-empty consecutive parts $T = A + B + C$ (where $+$ denotes string concatenation), such that each part $A, B, C$ is a homophone replacement of some string in $S$. Each splitting corresponds to one string triple $(A,B,C)$, and we call this triple a homophone triple of string $T$. Two homophone triples $(A_1, B_1, C_1)$ and $(A_2, B_2, C_2)$ are essentially different if and only if $A_1 \neq A_2$ or $B_1 \neq B_2$ or $C_1 \neq C_2$.

Now you are given $n$ strings $S_1, S_2, \dots, S_n$ as the language set, and $m$ strings $T_1, T_2, \dots, T_m$ as the language materials to be analyzed.
For each $T_i$, please help little $\omega$ find how many essentially different homophone triple schemes there are.

Input Format

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

The next $n$ lines each contain a string $S_i$, representing a word in the language set.

The next $m$ lines each contain a string $T_i$, representing the material to be analyzed.

Output Format

Output $m$ lines. The $j$-th line ($1 \le j \le m$) contains a non-negative integer, indicating how many essentially different homophone triples $T_j$ has.

1 1
abbcabb
abbcabbcabb

12

Hint

Sample 1 Explanation

The $12$ essentially different homophone triples are as follows:

• $(\text{a},\text{bbcabb},\text{cabb})$
• $(\text{ab},\text{bcabb},\text{cabb})$
• $(\text{abb},\text{cabb},\text{cabb})$
• $(\text{abbc},\text{a},\text{bbcabb})$
• $(\text{abbc},\text{ab},\text{bcabb})$
• $(\text{abbc},\text{abb},\text{cabb})$
• $(\text{abbc},\text{abbc},\text{abb})$
• $(\text{abbc},\text{abbca},\text{bb})$
• $(\text{abbc},\text{abbcab},\text{b})$
• $(\text{abbca},\text{b},\text{bcabb})$
• $(\text{abbca},\text{bb},\text{cabb})$
• $(\text{abbcab},\text{b},\text{cabb})$

Constraints

Let $|X|$ be the length of string $X$, $L_1 = \sum\limits_{i = 1}^{n} |S_i|$, and $L_2 = \sum\limits_{i = 1}^{m} |T_i|$. For all testdata, it is guaranteed that:

• $1 \le n , m \le 10^5$;
• $1 \le |S_i|$, $3 \le |T_i|$;
• $1 \le L_1 \le 5 \times 10^5$, $3 \le L_2 \le 3 \times 10^5$;
• For all $1 \le i \le n$, each $S_i$ contains only uppercase and lowercase English letters.
• For all $1 \le i \le m$, each $T_i$ contains only uppercase and lowercase English letters.

Special property A: $m = 1$.

Special property B: For all $1 \le i \le n$, each $S_i$ ends with z. For all $1 \le i \le m$, each $T_i$ does not contain z.

Translated by ChatGPT 5