P16693 Tokitsukaze and Palindrome Border

 However, for some reasons, this problem did not appear in [ Codeforces Round 789](https://codeforces.com/contests/1677,1678).

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)$$

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$.

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

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