背景

但由于一些原因，本题未能出现在 Codeforces Round 789 中。

题目描述

给定一个字符串 $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$。

输出格式

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

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

提示

样例一解释：

• $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$。