Description
给定一个串S和q组询问i,问其前i个子串构成的前缀Si有多少个Border。
一个串T称为另一个串S的Border,如果T既是S的前缀又是后缀。
Input
- 第一行是两个整数n,q,表示字符串长度和询问个数。
- 第二行是一个长为n,只包含小写英文字母的字符串。
- 接下来q行每行一个整数i≤n,表示一个询问。
Output
- 输出有q行,第i行表示对于第i个询问的答案。
Sample
Input
Output
Hint
- 对于全部10组数据,规模如下:
- n=10,100,1000,1000,10000,100000,100000,100000,100000,100000
- q=10,100,1000,1000,1,1,100000,100000,100000,100000