Barbarian Tablets

Time limit4sMemory limit768 MB

Summary

Each query asks how many words shown so far contain the tablet word of barbarian S as a contiguous substring.

Level: Medium7 of 10
Topics: String matching, Trie
Solved: No attempts yet

Problem

There are plenty of unusual people around. The ones we care about here are barbarians.

There are many barbarians, but only $N$ of them matter in this story, numbered 1 to $N$ . Every barbarian has one stone tablet, and a single word made of lowercase English letters is carved on it.

The barbarians play a game with their friend Tarzan. The game runs for $Q$ rounds, and Tarzan picks the type of each round.

First type: Tarzan shows the word $P$ to the barbarians.
Second type: Tarzan asks barbarian $S$ this question. "Out of all the words I have shown so far, how many of them contain the word carved on your tablet as a contiguous substring?"

The barbarians go wild easily and cannot keep up with the game. Answer each of Tarzan's questions for them.

Input

The first line contains the number of barbarians $N$ ( $1 \le N \le 10^5$ ).

Each of the next $N$ lines contains one word made of lowercase English letters. The word on line $i$ is the word carved on the tablet of barbarian $i$ .

The next line contains the number of rounds $Q$ ( $1 \le Q \le 10^5$ ).

Each of the following $Q$ lines describes one round and starts with the integer $O$ .

If $O$ is 1, the round is of the first type, and the word $P$ that Tarzan shows follows on the same line. $P$ is made of lowercase English letters.

If $O$ is 2, the round is of the second type, and the label $S$ ( $1 \le S \le N$ ) of the barbarian Tarzan asks follows on the same line.

The total length of the words carved on the tablets is at most $2 \times 10^6$ .

The total length of the words Tarzan shows is at most $2 \times 10^6$ .

Output

For each round of the second type, print one line with the answer. Line $i$ holds the answer to Tarzan's question in the $i$ th round of the second type.

If the same word is shown several times, every showing counts separately. If a tablet word occurs several times inside one shown word, that shown word still counts once. When no word has been shown yet, the answer is 0.

Notes

In the first sample the only word Tarzan shows is abca. The answer to the first question is 1, because the word a is a substring of abca. The answer to the second question is also 1, because abc is a substring of abca as well.

Examples2

Example 1
Input
```
3
a
bc
abc
3
1 abca
2 1
2 3
```
Expected output
```
1
1
```

Example 2

Input

7
abba
bbaa
b
bbaa
abba
a
ba
7
1 aaabbabbaab
2 7
1 baabaaa
1 aabbbab
2 3
1 aabba
2 3

Expected output

1
3
4