NC24902. Parco_Love_String
描述
众所周知，在算法竞赛中，出题人对他出的题的难度往往存在错误的估计。比如出题人本想出个简单题，没想到却出成了重坑细节题；本想出个中等难度题，结果却变成了防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个。