LCP Queries

A string $x$ is called a prefix of a string $y$ if $x$ can be obtained by repeatedly removing the last letter of $y$ zero or more times. For example, abac, aba, ab, a, and the empty string are the prefixes of abac.

For two strings $x$ and $y$, let $\text{LCP}(x, y)$ be the length of their longest common prefix. For example, the longest common prefix of abacab and abacbba is abac, so $\text{LCP}$ of the two is $4$. Every pair of strings has the empty string as a common prefix, so $\text{LCP}(x, y)$ is always defined.

You are given $n$ strings $s_1, \dots, s_n$ and $m$ strings $t_1, \dots, t_m$, all made of lowercase English letters. Then you are given $q$ queries. Each query is an integer sequence $a_1, \dots, a_k$. Let $u$ be the concatenation of $t_{a_1}, \dots, t_{a_k}$. For each query, compute $\sum_{i=1}^{n}{\text{LCP}(u, s_i)}$.

The input is a single test case in the following format.

$n$

$s_1$

$\vdots$

$s_n$

$m$

$t_1$

$\vdots$

$t_m$

$q$

$\text{query}_1$

$\vdots$

$\text{query}_q$

The first line has an integer $n$. Each of the next $n$ lines has a non-empty string $s_i$. The next line has an integer $m$. Each of the next $m$ lines has a non-empty string $t_j$. The next line has an integer $q$. Then $q$ queries follow, one per line, in this format.

$k$ $a_1$ $\cdots$ $a_k$

$k$ is a positive integer, the length of the integer sequence. Each $a_i$ is an integer between $1$ and $m$, inclusive.

The constraints are $1 \le n \le 200\,000$, $1 \le m \le 200\,000$, and $1 \le q \le 200\,000$. The sum of lengths of the $s_i$ is at most $200\,000$. The sum of lengths of the $t_i$ is at most $200\,000$. The sum of $k$ over all queries is at most $200\,000$.

Output $q$ lines. The $i$-th line contains the answer to the $i$-th query.