QUERYSTR - Query Problem

McFn interested in string problem recently. He found a interesting function and he felt he could use this function to invent a new match algorithm.

For a string S [1 ... n] and i ¡Ê [1, n], define F (i) is the length of the longest common suffix of S and S [1 ... i].
For example, for the string S [1 ... 11] = zaaxbaacbaa, then F (1) = 0, F (2) = 1, F (3) = 2 (note that S [1 ... 3] = zaa), F (4) = 0, ... ... F (10) = 1, F (11) = 11;
For the string S [1 ... n], i ¡Ê [1, n], S [i ... n] is its suffix;

Input

The first line is a integer T.the number of test cases
for each test case
The first line is a string S, composed of only lowercase letters,  len (s) is the length of s,  1 <= len (s) <= 1000000;
Next line, a number N (1 <= N <= 100000), denote that the number of queries;
The next N lines, each line contains a number x (1 <= x <= len (s)).

Output

For each x the output F (x);

Example

Input:
1
zaaxbaacbaa
11
1
2
3
4
5
6
7
8
9
10
11

Output: 0
1
2
0
0
1
3
0
0
1
11

Added by:Hemant Verma
Date:2009-11-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Alkhwarizm 2009

hide comments
2015-07-10 12:11:39 Stupid Dog
C++ : getline(cin,s) : WA ; cin >> s : AC
2015-06-29 11:21:00 THECOLDONE
i think test case are right ,easy one
2013-06-23 11:38:20 Rishav Goyal
@hemant, i think there is problem with testcases !!
2013-06-23 11:37:21 Rishav Goyal
i don understand,i am doing in log(N), still tle !!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.