Description

给定一个串\(S\)和\(q\)组询问\(i\)，问其前\(i\)个子串构成的前缀\(S_i\)有多少个\(Border\)。

一个串\(T\)称为另一个串\(S\)的\(Border\)，如果\(T\)既是\(S\)的前缀又是后缀。

Input

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

Output

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

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, 100000\)
• \(q = 10, 100, 1000, 1000, 1, 1, 100000, 100000, 100000, 100000\)