Substrings and Repetitions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Statement
Given a string S and several frequencies F_{i}. For each F_{i} output the number of substrings of S (the characters of substring should be contiguous) that occur at least F_{i} times in S. Note, that we consider two substrings distinct if they have distinct length, or they have distinct starting indices.
Input
The first line of input contains integer T, the number of test cases.
The first line of each test case contains string S (it contains only lowercase Latin letters). The second line of each test case contains an integer Q, that is the number of queries to be answered. Then Q lines follows containing F_{i} each.
Output
For each query, output the required answer.
Constraints
 1 ≤ S ≤ 200000
 1 ≤ Q ≤ 200000
 1 ≤ F_{i} ≤ 200000
 Sum of S over all test cases ≤ 200000
 Sum of Q over all test cases ≤ 200000
Example
Input: 1 aaeddf 4 1 2 3 4 Output: 21 4 0 0
Explanation
There are a total of 6*(6+1)/2 substrings, all of them occur at least once. So for F_{1}=1 answer is equal to 21. Note that substring "a" is repeated 2 times in S, both the instances are added to the answer.
Look at F_{2}=2. Substring "a" and substring "d" occurs 2 times each in S. The answer for F_{2} is 4, that is all the occurrences of "a" and "d".
There are no substrings which repeat more than twice. So rest answers are 0
Author:  anudeep2011 
Tester:  gerald 
Editorial  http://discuss.codechef.com/problems/ANUSAR 
Tags  anudeep2011, cook46, disjointset, mediumhard, segmenttree, stack, suffixarray, suffixtrees 
Date Added:  3032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 