Suffix Pair LCP Sum

Given a string \(S\) of length \(n\) that consists only of lowercase letters (with indices \(1\) to \(n\)), you are to answer several queries.

Each query provides a set of starting positions in \(S\), each representing a suffix \(S[i]\). For each query, compute the sum of the lengths of the Longest Common Prefix (LCP) for every distinct pair of these suffixes. Note that each pair is considered only once.

The LCP of two strings \(A\) and \(B\) is defined as the maximum length \(\ell\) such that \(A[1..\ell]=B[1..\ell]\), written in \(\LaTeX\) as:

\( \text{LCP}(A, B)=\max\{\ell\,|\,A[1..\ell]=B[1..\ell]\} \)

inputFormat

The input begins with a single line containing the string \(S\).

The second line contains an integer \(q\) representing the number of queries.

Each of the next \(q\) lines describes a query in the following format:

\(k\, p_1\, p_2\, \dots\, p_k\)

where \(k\) is the number of suffixes to consider and \(p_1, p_2, \dots, p_k\) are the starting indices (1-indexed) of the suffixes in \(S\).

outputFormat

For each query, output a single line containing one integer: the sum of the LCP lengths of each distinct pair of suffixes specified in the query.

sample

ababa
2
2 1 3
3 2 4 5

3
2