如今，世界上有许多奇特的人。我们不在此赘述，而是将目光投向某一类人——对我们而言最有趣的人。当然，我们说的是野蛮人！

这里有许多野蛮人，但只有少数是真正重要的。故事中有 $N$ 个重要的野蛮人，用 $1$ 到 $N$ 的整数表示。他们每个人都有一块石板，上面写着一个仅由英文小写字母组成的单词。

我们的野蛮人们正在和他们的好朋友泰山（Tarzan）玩一个有趣的游戏。

游戏共进行 $Q$ 轮。有两种轮次类型，每轮的类型由泰山决定：

• 第一种类型：泰山向野蛮人们展示一个单词 $P$。
• 第二种类型：泰山向编号为 $S$ 的野蛮人提出以下问题：“在我目前展示过的所有单词中，有多少个单词满足：你石板上的单词是它的连续子串？”

鉴于野蛮人们经常情绪狂躁，无法真正集中注意力并跟上游戏的进程，他们需要你的帮助。请帮助野蛮人们正确回答泰山的每个问题。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示野蛮人的数量。

接下来的 $N$ 行，每行包含一个仅由英文小写字母组成的单词，第 $i$ 个单词对应编号为 $i$ 的野蛮人石板上的单词。

之后包含一个整数 $Q$（$1 \le Q \le 10^5$），表示游戏的轮数。

接下来的 $Q$ 行描述游戏的每一轮，第 $i$ 行描述第 $i$ 轮游戏。

每行将包含一个整数 $O$。

• 当 $O$ 等于 $1$ 时，表示第一种类型的轮次，同一行后面会跟着展示的单词 $P$，由英文小写字母组成。
• 当 $O$ 等于 $2$ 时，表示第二种类型的轮次，同一行后面会跟着一个整数 $S$（$1 \le S \le N$），表示被泰山提问的野蛮人的编号。

所有写在野蛮人石板上的单词总长度不超过 $2 \cdot 10^6$。

泰山展示给野蛮人的所有单词总长度不超过 $2 \cdot 10^6$。

输出格式

对于每个第二种类型的轮次，输出一行。第 $i$ 行必须包含第 $i$ 个第二种类型轮次中泰山提问的正确答案。

子任务

在占总分 50% 的测试数据中，满足 $N \le 20\,000$。

样例

输入 1

3
a
bc
abc
3
1 abca
2 1
2 3

输出 1

1
1

输入 2

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

输出 2

1
3
4

说明

第一个样例的解释：

泰山展示的唯一单词是 abca。

第一个问题的答案显然是 $1$，因为单词 a 是单词 abca 的子串。

第二个问题的答案也是 $1$，因为单词 abc 是单词 abca 的子串。