Description

请注意本题特殊的时间限制。

给定一个长为 $n$ 的串 $s$。称子串 $s[i \dots j]$ 的中心是 $\frac{i + j}{2}$。

现在你要回答 $q$ 次询问，每次询问给出一个 $k$，问所有中心为 $\frac{k}{2}$ 的子串的 border 个数之和。

border 的定义如下：一个非空字符串 $t$ 是另一个字符串 $s$ 的 border，当且仅当 $t$ 既是 $s$ 的前缀，也是 $s$ 的后缀。例如，对任一个非空串 $s$，$s$ 本身就是一个 $s$ 的 border。

Input Format

从标准输入读入数据。

第一行包含两个正整数 $n (1 \leq n \leq 10^6), q (1 \leq q \leq 20)$，表示输入字符串 $s$ 的长度及询问次数。

第二行包含一个长度为 $n$ 的字符串 $s$，由英文小写字母组成。

接下来 $q$ 行，每行一个整数 $k (2 \leq k \leq 2n)$，表示一组询问。

Output Format

输出到标准输出。

输出 $q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

9 6
bbabbbbaa
2
5
10
11
14
15

1
3
8
9
3
2

Hint

【样例 1 解释】

当 $k = 2$ 时，以 $k/2$ 为中心的子串只有 $s[1 \dots 1] = \tt b$，border 数为 $1$。

当 $k = 5$ 时，以 $k/2$ 为中心的子串有 $s[2 \dots 3] = \tt {ba}, s[1 \dots 4] = \tt{bbab}$，border 数分别为 $1,2$。

当 $k = 10$ 时，以 $k/2$ 为中心的子串有 $s[5 \dots 5] = \tt{b}, s[4 \dots 6] = \tt{bbb}, s[3 \dots 7] = \tt{abbbb}, s[2 \dots 8] = \tt{babbbba}, s[1 \dots 9] = \tt{bbabbbbaa}$，border 数分别为 $1,3,1,2,1$。