P5840 [COCI 2014/2015 #5] Divljak

Alice 有 $n$ 个字符串 $S_1, S_2, \dots, S_n$，Bob 有一个字符串集合 $T$，一开始集合是空的。 接下来会发生 $q$ 个操作，操作有两种形式： 1. `1 P`：Bob 往自己的集合里添加了一个字符串 $P$。 2. `2 x`：Alice 询问 Bob，集合 $T$ 中有多少个字符串包含串 $S_x$（我们称串 $A$ 包含串 $B$，当且仅当 $B$ 是 $A$ 的子串）。

第一行一个整数 $n$。 接下来 $n$ 行，每行一个字符串 ${S}_i$。 接下来一行一个整数 $q$。 接下来 $q$ 行，每行一个操作。

对每个 `2 x` 操作，一行一个整数，表示答案。

对于 $50\%$ 的数据，$n\le 20000$。 对于 $100\%$ 的数据，$1\le n, q\le 10^5$，字符串由小写字母构成，$S$ 中所有字符串的长度之和与所有 $P$ 的长度之和分别 $\le 2\times 10^6$。 译自 [COCI 2014/2015 CONTEST #5](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。