LCP 질의

문자열 $x$가 문자열 $y$의 접두사(prefix)라는 것은 $y$의 마지막 글자를 0번 이상 반복해서 지워서 $x$를 얻을 수 있다는 뜻이다. 예를 들어 abac, aba, ab, a, 빈 문자열은 모두 abac의 접두사이다.

두 문자열 $x$, $y$에 대해 $\text{LCP}(x, y)$는 둘의 가장 긴 공통 접두사의 길이이다. 예를 들어 abacab과 abacbba의 가장 긴 공통 접두사는 abac이므로 두 문자열의 $\text{LCP}$는 $4$이다. 두 문자열은 항상 빈 문자열을 공통 접두사로 가지므로 $\text{LCP}(x, y)$는 언제나 정의된다.

소문자 영문자로 이루어진 $n$개의 문자열 $s_1, \dots, s_n$과 $m$개의 문자열 $t_1, \dots, t_m$이 주어진다. 이어서 $q$개의 질의가 주어진다. 각 질의는 정수 수열 $a_1, \dots, a_k$로 주어진다. $u$를 $t_{a_1}, \dots, t_{a_k}$를 이어 붙인 문자열이라 할 때, 각 질의마다 $\sum_{i=1}^{n}{\text{LCP}(u, s_i)}$를 구하라.

입력은 다음 형식으로 하나의 테스트 케이스가 주어진다.

$n$

$s_1$

$\vdots$

$s_n$

$m$

$t_1$

$\vdots$

$t_m$

$q$

$\text{query}_1$

$\vdots$

$\text{query}_q$

첫 줄에 정수 $n$이 주어진다. 다음 $n$개 줄에는 비어 있지 않은 문자열 $s_i$가 한 줄에 하나씩 주어진다. 다음 줄에는 정수 $m$이 주어진다. 이어서 $m$개 줄에 비어 있지 않은 문자열 $t_j$가 한 줄에 하나씩 주어진다. 다음 줄에는 정수 $q$가 주어지고, 이어서 $q$개의 질의가 한 줄에 하나씩 주어진다. 각 질의는 다음 형식이다.

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

$k$는 정수 수열의 길이를 나타내는 양의 정수이다. 각 $a_i$는 1 이상 $m$ 이하의 정수이다.

제약 조건은 $1 \le n \le 200\,000$, $1 \le m \le 200\,000$, $1 \le q \le 200\,000$이다. $s_i$ 길이의 합은 $200\,000$을 넘지 않는다. $t_i$ 길이의 합도 $200\,000$을 넘지 않는다. 모든 질의의 $k$의 합은 $200\,000$을 넘지 않는다.

$q$개의 줄을 출력하라. $i$번째 줄에는 $i$번째 질의의 답을 출력한다.