#3605. [Coci2015]Divljak

[Coci2015]Divljak

Description

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

接下来会发生q个操作,操作有两种形式:

“1 P”,Bob往自己的集合里添加了一个字符串P。

“2 x”,Alice询问Bob,集合T中有多少个字符串包含串S_x。(我们称串A包含串B,当且仅当B是A的子串)

Bob遇到了困难,需要你的帮助。

Format

Input

第1行,一个数n;

接下来n行,每行一个字符串表示S_i;

下一行,一个数q;

接下来q行,每行一个操作,格式见题目描述。

Output

对于每一个Alice的询问,帮Bob输出答案。

Samples

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

Limitation

【数据范围】

1 <= n,q <= 100000;

Alice和Bob拥有的字符串长度之和各自都不会超过 2000000;

字符串都由小写英文字母组成。