Problem Description

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$).

Input Format

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.

Output Format

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

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

1
2
1

Hint

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。

Translated by ChatGPT 5