说明

对于一个字符串 $y$，如果字符串 $x$ 可以通过零次或多次移除 $y$ 的最后一个字母得到，则称 $x$ 是 $y$ 的一个前缀。例如，“abac”、“aba”、“ab”、“a” 以及空字符串都是 “abac” 的前缀。

对于两个字符串 $x$ 和 $y$，令 $\text{LCP}(x, y)$ 表示 $x$ 和 $y$ 的最长公共前缀的长度。例如，$\text{LCP}(\text{“abacab”}, \text{“abacbba”}) = 4$，因为这两个字符串的最长公共前缀是 “abac”。注意，对于任意字符串 $x$ 和 $y$，$\text{LCP}(x, y)$ 总是有定义的，因为至少空字符串是它们的公共前缀之一。

给定 $n$ 个小写英文字母串 $s_1, \ldots, s_n$ 和 $m$ 个小写英文字母串 $t_1, \ldots, t_m$。接下来，给定 $q$ 次查询。每次查询给定一个整数序列 $a_1, \ldots, a_k$。令 $u$ 为 $t_{a_1}, \ldots, t_{a_k}$ 的连接。你的任务是计算 $\sum_{i=1}^{n} \text{LCP}(u, s_i)$。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &n \\ &s_1 \\ &\vdots \\ &s_n \\ &m \\ &t_1 \\ &\vdots \\ &t_m \\ &q \\ &\text{Query}_1 \\ &\vdots \\ &\text{Query}_q \end{aligned}$$

第一行包含一个整数 $n$。接下来的 $n$ 行，每行包含一个非空的小写英文字母串 $s_i$。接下来一行包含一个整数 $m$。接下来的 $m$ 行，每行包含一个非空的小写英文字母串 $t_j$。

接下来一行包含一个整数 $q$。随后按顺序给出 $q$ 次查询。每次查询以单独一行的形式给出，格式如下：

$$k \ a_1 \ \ldots \ a_k$$

其中 $k$ 是一个正整数，表示本次查询的整数序列的长度。每个 $a_i$ 是一个介于 $1$ 到 $m$ 之间（含）的整数。

可以假设 $1 \leq n \leq 200,000$，$1 \leq m \leq 200,000$ 且 $1 \leq q \leq 200,000$。所有 $s_i$ 的长度之和不超过 $200,000$。类似地，所有 $t_i$ 的长度之和不超过 $200,000$。所有查询的 $k$ 值之和不超过 $200,000$。

输出格式

输出 $q$ 行。第 $i$ 行应为第 $i$ 次查询的答案。

5
abcde
aaa
a
ab
bcd
5
a
bc
de
aaaa
b
5
1 1
3 1 2 3
2 2 3
5 5 4 3 2 1
3 3 3 3

4
9
3
1
0

提示

翻译由 DeepSeek V3.2 完成