33448번 - 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)$.