#3733. 「COCI 2015.1」DIVLJAK

题目描述

译自 COCI 2014/2015 Contest #5 T6「DIVLJAK」。

Alice 有 $n$ 个字符串 $S_1, S_2, \ldots, S_n$，Bob 有一个字符串集合 $T$，一开始集合是空的。

接下来会发生 $q$ 个操作，操作有两种形式：

• 1 P：Bob 往自己的集合里添加了一个字符串 $P$。
• 2 x：Alice 询问 Bob，集合 $T$ 中有多少个字符串包含串 $S_x$（我们称串 $A$ 包含串 $B$，当且仅当 $B$ 是 $A$ 的子串）。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行一个字符串 $S_i$。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行一个操作。

输出格式

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

样例

输入

3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3

输出

1
2
1

数据范围与提示

对于 $100\%$ 的数据，$1 \leq n,q \leq 10^5$，字符串由小写字母构成，所有字符串的总长 $\le 2 \times 10^6$。