Border计数

Border计数

Description

给定一个串SSqq组询问ii,问其前ii个子串构成的前缀SiS_i有多少个BorderBorder

一个串TT称为另一个串SSBorderBorder,如果TT既是SS的前缀又是后缀。

Input

  • 第一行是两个整数n,qn, q,表示字符串长度和询问个数。
  • 第二行是一个长为nn,只包含小写英文字母的字符串。
  • 接下来qq行每行一个整数ini\le n,表示一个询问。

Output

  • 输出有qq行,第ii行表示对于第ii个询问的答案。

Sample

Input

10 5
aabababaab
4
5
6
9
10

Output

1
0
1
2
1

Hint

  • 对于全部10组数据,规模如下:
  • n=10,100,1000,1000,10000,100000,100000,100000,100000,100000n = 10, 100, 1000, 1000, 10000, 100000, 100000, 100000, 100000, 100000
  • q=10,100,1000,1000,1,1,100000,100000,100000,100000q = 10, 100, 1000, 1000, 1, 1, 100000, 100000, 100000, 100000

信息

难度
5
分类
(无)
标签
(无)
递交数
19
已通过
12
通过率
63%
上传者