B. 回响形态 / String

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

题目描述

请注意本题特殊的时间限制。 给定一个长为 n 的串 s。称子串 s[i ... j] 的中心是 (i + j) / 2。 现在你要回答 q 次询问，每次询问给出一个 k，问所有中心为 k / 2 的子串的 border 个数之和。 border 的定义如下： 一个非空字符串t 是另一个字符串 s 的 border， 当且仅当t 既 是 s 的前缀， 也是s 的后缀。 例如， 对任一个非空字符串s，s 本身就是一个 s 的 border。

输入格式

从标准输入读入数据。 第一行包含两个正整数 n(1 ≤ n ≤ 10^6), q(1 ≤ q ≤ 20)，表示输入字符串 s 的长度 及询问次数。 第二行包含一个长度为 n 的字符串 s，由英文小写字母组成。 接下来 q 行，每行一个整数 k(2 ≤ k ≤ 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 ... 1] = b，border 数为 1。 当 k = 5 时， 以k/2 为中心的子串有 s[2 ... 3] = ba, s[1 ... 4] = bbab，border 数分别 为 1,2。 当 k = 10 时，以 k/2 为中心的子串有 s[5 ... 5] = b, s[4 ... 6] = bbb, s[3 ... 7] = abbbb, s[2 ... 8] = babbbba, s[1 ... 9] = bbabbbbaa，border 数分别为 1,3,1,2,1。