회문 문자열

문자열 $S = S_1 S_2 \ldots S_{|S|}$와 $q$개의 질의가 주어진다. 각 질의에서는 문자열 $t = t_1 t_2 \ldots t_{|t|}$가 주어지며, $1 \le \ell \le r \le |S|$를 만족하는 쌍 $(\ell, r)$ 중에서 $t_1 t_2 \ldots t_{|t|} S_{\ell} S_{\ell + 1} \ldots S_r$이 회문이 되는 쌍의 개수를 구한다. 여기서 회문이란 $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$이 성립하는 경우를 말한다.

첫째 줄에 문자열 $S$의 길이 $n$과 질의의 개수 $q$가 주어진다 ($1 \le n \le 10^6$, $1 \le q \le 10^5$). 둘째 줄에는 문자열 $S$가 주어진다. 이어지는 $q$개의 줄에는 각각 질의 문자열 $t$가 하나씩 주어진다. 모든 문자열은 소문자 영문자로만 이루어지며, $\sum |t| \le 10^6$이다.

각 질의에 대해 조건을 만족하는 쌍의 개수를 한 줄에 하나의 정수로 출력한다.

• 첫 번째 질의에서 쌍은 $(2, 3)$, $(3, 3)$, $(7, 8)$, $(8, 8)$ 네 개이며, 결합 문자열은 차례로 pcp, pp, pmp, pp이다.
• 두 번째 질의에서 쌍은 $(1, 2)$, $(2, 2)$, $(2, 5)$, $(3, 4)$, $(4, 4)$, $(4, 5)$, $(5, 5)$ 일곱 개이다.
• 세 번째 질의에서 쌍은 $(1, 3)$, $(2, 3)$, $(3, 3)$, $(8, 8)$ 네 개이다.