Background

However, for some reasons, this problem did not appear in Codeforces Round 789.

Problem Description

Given a string $s$. Define:

• $\operatorname{pre}(s, len)$ as the prefix substring of $s$ with length $len$.
• $\operatorname{suf}(s, len)$ as the suffix substring of $s$ with length $len$.
• $|s|$ as the length of the string $s$.

For any two strings $s$ and $t$, define the function $f(s, t)$ as:

$$f(s, t) = \sum_{len=1}^{\min(|s|, |t|)} \operatorname{val}(len)$$

Here, $\operatorname{val}(len)$ is computed as follows:

$$\operatorname{val}(len) = \begin{cases} len, & \text{if } \operatorname{pre}(s, len) = \operatorname{suf}(t, len) \text{ and } \operatorname{pre}(s, len) \text{ is a palindrome} \\ 0, & \text{otherwise} \end{cases}$$

Note: A palindrome is a string that reads the same forward and backward, such as a, aa, or aba.

Now Tokitsukaze has $n$ strings $s_1, s_2, \dots, s_n$. At the same time, she asks $q$ queries.
Each query gives a set $B$ containing $k$ positive integers, representing the indices of disabled strings. For each query, compute:

$$\sum_{i \notin B} \sum_{j \notin B} f(s_i, s_j)$$

Input Format

The first line contains an integer $n$ ($1 \leq n \leq 3 \cdot 10^5$), denoting the number of strings.

The next $n$ lines each contain a string $s$ consisting of lowercase letters ($1 \leq |s| \leq 3 \cdot 10^5$).

The next line contains a positive integer $q$ ($1 \leq q \leq 3 \cdot 10^5$), denoting the number of queries.

The next $q$ lines each describe a query with $k + 1$ integers. The first integer is $k$ ($0 \leq k_i \leq n$), followed by $k$ pairwise distinct positive integers $B_j$ ($1 \leq B_j \leq n$), representing the set of disabled indices.

It is guaranteed that $\sum |s|$ and $\sum k$ do not exceed $3 \cdot 10^5$.

Output Format

For each query, output one line containing one integer representing the answer.

2
a
aaa
4
0
1 1
1 2
2 1 2

9
6
1
0

3
a
aa
aaba
3
0
2 1 3
1 1

13
3
8

Hint

Explanation for Sample 1:

• $f(s_1, s_1) = 1$
• $f(s_1, s_2) = 1$
• $f(s_2, s_1) = 1$
• $f(s_2, s_2) = 1 + 2 + 3 = 6$

The answer to the first query is $f(s_1, s_1) + f(s_1, s_2) + f(s_2, s_1) + f(s_2, s_2) = 9$.

The answer to the second query is $f(s_2, s_2) = 6$.

The answer to the third query is $f(s_1, s_1) = 1$.

For the fourth query, since all indices are disabled, the answer is $0$.

Translated by ChatGPT 5