P16693 Tokitsukaze and Palindrome Border

 但由于一些原因，本题未能出现在 [ Codeforces Round 789](https://codeforces.com/contests/1677,1678) 中。

给定一个字符串 $s$。定义： * $\operatorname{pre}(s, len)$ 表示 $s$ 长度为 $len$ 的**前缀**子串； * $\operatorname{suf}(s, len)$ 表示 $s$ 长度为 $len$ 的**后缀**子串； * $|s|$ 表示字符串 $s$ 的长度。 对于任意两个字符串 $s$ 和 $t$，定义函数 $f(s, t)$ 为： $$f(s, t) = \sum_{len=1}^{\min(|s|, |t|)} \operatorname{val}(len)$$ 其中，$\operatorname{val}(len)$ 的计算方式如下： $$\operatorname{val}(len) = \begin{cases} len, & \text{若 } \operatorname{pre}(s, len) = \operatorname{suf}(t, len) \text{ 且 } \operatorname{pre}(s, len) \text{ 是回文串} \\ 0, & \text{其他情况} \end{cases}$$ *注： 回文串是指正着读和反着读都相同的字符串，例如 `a`、`aa` 或 `aba`。* 现在 Tokitsukaze 有 $n$ 个字符串 $s_1, s_2, \dots, s_n$。同时，她提出了 $q$ 个询问。 每个询问将给出一个包含 $k$ 个正整数的集合 $B$，表示被禁用的字符串下标。对于每个询问，求： $$\sum_{i \notin B} \sum_{j \notin B} f(s_i, s_j)$$

第一行包含一个整数 $n$ ($1 \leq n \leq 3 \cdot 10^5$)，表示字符串的数量。 接下来 $n$ 行，每行包含一个由小写字母组成的字符串 $s$ ($1 \leq |s| \leq 3 \cdot 10^5$)。 接下来一行包含一个正整数 $q$ ($1 \leq q \leq 3 \cdot 10^5$)，表示询问的数量。 接下来的 $q$ 行，每行包含 $k+1$ 个整数表示一个询问。第一个整数是 $k$ ($0 \leq k_i \leq n$)，紧接着 $k$ 个**互不相同**的正整数 $B_j$ ($1 \leq B_j \leq n$)，表示被禁用的下标集合。 保证 $\sum |s|$ 和 $\sum k$ 都不超过 $3 \cdot 10^5$。

对于每个询问，输出一行包含一个整数表示答案。

样例一解释： - $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$ 第一个询问的答案为 $f(s_1,s_1) + f(s_1,s_2) + f(s_2,s_1) + f(s_2,s_2) = 9$。 第二个询问的答案为 $f(s_2,s_2) = 6$。 第三个询问的答案为 $f(s_1,s_1) = 1$。 第四个询问，由于所有下标都被禁用了，所以答案为 $0$。