Problem H: Parco_Love_String

Problem H: Parco_Love_String

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board]

Description

It is known to all that, in an algorithm contest, the questions setters often have an inaccurate estimation on the questions they've set. Sometimes they wants to set up easy questions but some traps obstruct the contestants. Sometimes who want to set up a question of median difficulty but finally no one AC. Therefore, it's of great importance to hire an experienced question setter when holding a comfortable contest.

After CC set up several questions, he invited Little Horse to check the difficulties. Although Little Horse is very clever and quickly came up with ideas to solve the questions, he thought they may be slightly difficult for most contestants. So he is adding an easy question.

Little Horse has a string \(S\) which only consists of lowercase letters, and he is asking you about the string. In each query, Little Horse gives an integer \(i\), meaning that he cut \(S\) into two parts between the \(i\)-th and \((i+1)\)-th characters. So we get two substrings \(S[1,i]\) and \(S[i+1, |S|]\). Denote \(A=S[1,i], B=S[i+1, |S|]\). Now, considering all the consecutive substrings of \(A\) and all the consecutive substrings of \(B\), Little Horse wants to know how many pairs of same substrings are there between \(A\) and \(B\). Formally, he wants to know:
\[
ans = \sum_{1\leq l_1\leq r_1\leq |A|} \sum_{1\leq l_2\leq r_2\leq |B|} [\space A[l_1, ..., r_1] == B[l_2, ..., r_2] \space]
\]
where
\[
[x] = \begin{cases}
1 \space(x=True) \\
0 \space(x=False)
\end{cases}
\]
Could you help Little Horse?

Input

The first line contains a string \(S (1\leq |S|\leq 1000)\), which only consists of lowercase letters.

The second line contains an integer \(T(1\leq T\leq 10^5)\), representing the number of queries.

Then \(T\) lines follow. Each test case contains an integer \(i\) in one line, representing a query.

Output

For each query, output an integer \(ans\) in a line as the answer.

Sample Input

ababa
4
1
2
3
4

Sample Output

2
4
4
2

HINT

For the query with \(i=3\), the original string is cut into two parts \(A=aba, B=ba\).



Then the substrings of \(A\) are \(a,a,b,ab,ba,aba\) and the substrings of \(B\) are \(a,b,ba\).



Therefore the pairs of same substrings between \(A,B\) are \((a,a), (a,a), (b,b), (ba,ba)\), so the answer is \(4\).




[Submit][Status]