4442 - [Swerc2015]Text Processor

给你一个字符串，每次询问你一个长度为w的区间[i,i-w+1]中不同的子串个数

Input

第一行一个字符串D。 第二行两个正整数Q和w，分别表示询问总数和所有询问的区间长度 接下来Q行，每行一个正整数，表示询问区间的起始位置 1<=|D|<=100000 1<=Q<=100000 1<=W<=|D| 1<=i<=|D|-w+1

Output

对于每个询问，输出一个整数，表示该区间的不同子串个数。

Examples

Input

样例输入1：
acat
2 3
1
2
样例输入2：
portoisamazing
2 7
6
3

Output

样例输出1：
5
6

样例输出2：
26
28

样例解释1：
第一个询问询问区间[1,3]->(aca)该区间有5个不同的子串(a,c,ac,ca,aca)
第二个询问询问区间[2,4]->(cat)该区间有6个不同的子串(c,a,t,ca,at,cat)
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题