给定一个字符串 $S = S_1S_2 \dots S_{|S|}$ 和 $q$ 次询问。在每次询问中，给定一个字符串 $t = t_1t_2 \dots t_{|t|}$，你需要确定满足 $1 \le \ell \le r \le |S|$ 的数对 $(\ell, r)$ 的数量，使得组合字符串 $t_1t_2 \dots t_{|t|}S_\ell S_{\ell+1} \dots S_r$ 是一个回文串，即满足：

$$t_1t_2 \dots t_{|t|}S_\ell S_{\ell+1} \dots S_r = S_r S_{r-1} \dots S_\ell t_{|t|} t_{|t|-1} \dots t_1$$

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^6, 1 \le q \le 10^5$)，分别表示字符串 $S$ 的长度和询问次数。

第二行包含一个字符串 $S$。

接下来的 $q$ 行，每行包含一个字符串 $t$，表示一次询问。

保证所有字符串仅包含小写英文字母，且 $\sum |t| \le 10^6$。

输出格式

对于每次询问，输出一行，包含一个整数，表示满足条件的数对数量。

样例

输入 1

8 3
icpccamp
p
c
pc

输出 1

4
7
4

说明

• 对于第一次询问，4 个数对分别是 $(2, 3), (3, 3), (7, 8)$ 和 $(8, 8)$，对应的组合字符串分别为 “pcp”, “pp”, “pmp”, “pp”。
• 对于第二次询问，7 个数对分别是 $(1, 2), (2, 2), (2, 5), (3, 4), (4, 4), (4, 5)$ 和 $(5, 5)$。
• 对于第三次询问，4 个数对分别是 $(1, 3), (2, 3), (3, 3)$ 和 $(8, 8)$。