Parco_Love_String
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

众所周知,在算法竞赛中,出题人对他出的题的难度往往存在错误的估计。比如出题人本想出个简单题,没想到却出成了重坑细节题;本想出个中等难度题,结果却变成了防AK题。因此,为了让一场比赛能有良好的体验,有一个靠谱的验题人是非常重要的。

CC出好题目后,便拿给小马哥看。不出所料,这些题目小马哥全都是看一眼就会做,但他觉得这对于参赛选手来说还是有点难。为了避免CC被喷成毒瘤出题人,小马哥准备加一道签到题。

小马哥有一个只由小写字母组成的字符串S,他会问你一些关于这个字符串的问题。小马哥每次提问时会给你一个整数i,意思是要把字符串S在第i和第i+1个字符之间切断,这样便得到两个新串S[1,i]及S[i+1,|S|]。记A=S[1,i],B=S[i+1,|S|]。现在,先考虑A的所有连续子串,再考虑B的所有连续子串,小马哥问你A,B之间相同子串对有多少个。

也就是说,小马哥想让你计算下面这个式子:



其中,求和式右边的式子是这样一个函数:



你能解决小马哥的问题,并签到成功吗?

输入描述:

第一行是一个字符串S(1≤|S|≤1000),保证只由小写字母组成。
第二行是一个正整数T(1≤T≤105),表示询问次数。
接下来T行,每行一个整数i(1≤i≤n−1),表示一个询问。

输出描述:

对于每个询问,输出一行一个整数表示对应询问的ans,意义如题目描述中所述。
示例1

输入

复制
ababa
4
1
2
3
4

输出

复制
2
4
4
2

说明

对于i=3这个询问,原串被拆分成 A=aba,B=ba。
此时A的所有子串为:a,a,b,ab,ba,aba;B的所有子串为:a,b,ba。
因此A,B之间相同子串对为:(a,a),(a,a),(b,b),(ba,ba),共计4个。