Byteasar 在拜特兰计算生物学中心工作。他刚刚收到了一串长度为 $n$ 的基因序列。他的任务是找出该序列中频繁出现的循环片段。

Byteasar 的序列可以表示为一个由大写英文字母组成的字符串 $s = s_{1}\ldots s_{n}$。$s$ 的一个循环片段是指一个字符串 $t$，满足 $t$ 的所有循环移位$^{1}$均为 $s$ 的子串。

Byteasar 对给定长度 $m$ 的循环片段感兴趣。对于 $s$ 的一个给定循环片段 $t$，我们定义 $t$ 在 $s$ 中的循环出现次数为 $t$ 的所有不同循环移位在 $s$ 中出现的总次数。Byteasar 想要找到 $s$ 中长度为 $m$ 且具有最大循环出现次数的循环片段。请编写一个程序来帮助他。

$^{1}$一个字符串的循环移位是通过将其最后一个字母移动到开头（可能多次）而构成的。例如，ABAABA 有三个不同的循环移位，即 ABAABA、BAABAA 和 AABAAB。如果字符串 $u$ 是 $v$ 的连续若干个字符组成的子序列，则称 $u$ 是 $v$ 的子串。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 500\,000$, $1 \le q \le 8$)，分别表示基因序列的长度和需要回答的询问次数。第二行包含一个由 $n$ 个大写英文字母组成的字符串 $s$。接下来的 $q$ 行包含数字 $m_{i}$ ($2 \le m_{i} \le n$)，定义了需要考虑的循环片段的长度。

输出格式

程序应输出 $q$ 行。第 $i$ 行应包含一个整数，表示 $s$ 中长度为 $m_{i}$ 的循环片段所能达到的最大循环出现次数。

样例

输入 1

16 2
AABAABACDABAABAA
6
3

输出 1

4
10

说明

循环片段 AABAAB 在给定的字符串中出现了 4 次：一次作为 AABAAB，两次作为 ABAABA，一次作为 BAABAA。循环片段 AAB 在该字符串中出现了 10 次。