时间限制： 0.5 秒 空间限制： 1024 MiB

题目描述

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

给定一个长为 \(n\) 的串 \(s\)。称子串 \(s[i \ldots j]\) 的中心是 \((i + j) / 2\)。

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

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

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

样例

样例 1 输入

9 6
bbabbbbaa
2
5
10
11
14
15

样例 1 输出

1
3
8
9
3
2

样例 1 解释

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

当 \(k = 5\) 时，以 \(k / 2\) 为中心的子串有 \(s[2 \ldots 3] = ba\)、\(s[1 \ldots 4] = bbab\)，border 数分别为 \(1, 2\)。

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