Palindrome Strings

You are given a string $S = S_1 S_2 \ldots S_{|S|}$ and $q$ queries. In each query, a string $t = t_1 t_2 \ldots t_{|t|}$ is given, and you should determine the number of pairs $(\ell, r)$ such that $1 \le \ell \le r \le |S|$ and the combined string $t_1 t_2 \ldots t_{|t|} S_{\ell} S_{\ell + 1} \ldots S_r$ is a palindrome, which means that $$t_1 t_2 \ldots t_{|t|} S_{\ell} S_{\ell + 1} \ldots S_r = S_r S_{r - 1} \ldots S_{\ell} t_{|t|} t_{|t| - 1} \ldots t_1\text{.}$$

The first line contains two integers $n$ and $q$ ($1 \le n \le 10^6$, $1 \le q \le 10^5$) denoting the length of string $S$ and the number of queries, respectively.

The second line contains a single string $S$.

Each of the following $q$ lines contains a single string $t$ denoting a query.

It is guaranteed that all the strings only contain lowercase English letters and that $\sum |t| \le 10^6$.

For each query, output a single line containing one integer: the required number of pairs.

• For the first query, the 4 pairs are $(2, 3)$, $(3, 3)$, $(7, 8)$, and $(8, 8)$, and the combined strings are "pcp", "pp", "pmp", "pp", respectively.
• For the second query, the 7 pairs are $(1, 2)$, $(2, 2)$, $(2, 5)$, $(3, 4)$, $(4, 4)$, $(4, 5)$, and $(5, 5)$.
• For the third query, the 4 pairs are $(1, 3)$, $(2, 3)$, $(3, 3)$, and $(8, 8)$.