P5840 [COCI 2014/2015 #5] Divljak

Alice has $n$ strings $S_1, S_2, \dots, S_n$, and Bob has a set of strings $T$, which is empty at the beginning. Then there will be $q$ operations. There are two types of operations: 1. `1 P`: Bob adds a string $P$ to his set. 2. `2 x`: Alice asks Bob how many strings in set $T$ contain the string $S_x$ (we say string $A$ contains string $B$ if and only if $B$ is a substring of $A$).

The first line contains an integer $n$. The next $n$ lines each contain a string ${S}_i$. The next line contains an integer $q$. The next $q$ lines each contain one operation.

For each `2 x` operation, output one integer per line, representing the answer.

For $50\%$ of the testdata, $n \le 20000$. For $100\%$ of the testdata, $1 \le n, q \le 10^5$. All strings consist of lowercase letters. The sum of lengths of all strings in $S$ and the sum of lengths of all strings $P$ are each $\le 2 \times 10^6$. Translated from [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。 Translated by ChatGPT 5