Mishka 最喜欢的实验独立乐队最近发布了一张新专辑!那张专辑的歌曲有一个共同点。每个名称 $$$s_i$$$ 是以下类型之一:
- $$$1~c$$$ — 单个小写拉丁字母;
- $$$2~j~c$$$ — 名称 $$$s_j$$$ ($$$1 \le j < i$$$) 末尾附加一个小写拉丁字母。
歌曲编号从 $$$1$$$ 到 $$$n$$$。保证第一首歌曲的类型始终为 $$$1$$$。
Vova对新专辑相当感兴趣,但他确实没有时间完整地听它。因此,他向米什卡询问了一些问题,以确定某首歌是否值得听。问题具有以下格式:
- $$$i~t$$$ — 统计字符串 $$$t$$$ 在 $$$s_i$$$(专辑第 $$$i$$$ 歌曲的名称)中出现的次数,作为连续子字符串,$$$t$$$ 仅由小写拉丁字母组成。
Mishka 并没有质疑该信息的目的,但他很难提供它。你能帮 Mishka 回答 Vova 的所有问题吗?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — 专辑中的歌曲数。
接下来的 $$$n$$$ 行包含专辑中第 $$$i$$$ 歌曲的描述,格式如下:
- $$$1~c$$$ — $$$s_i$$$ 是单个小写拉丁字母;
- $$$2~j~c$$$ — $$$s_i$$$ 是名称 $$$s_j$$$ ($$$1 \le j < i$$$),末尾附加一个小写拉丁字母。
下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — Vova 的问题数。
接下来的 $$$m$$$ 行包含第 $$$j$$$ 个 Vova 问题的描述,格式如下:
- $$$i~t$$$ ($$$1 \le i \le n$$$, $$$1 \le |t| \le 4 \cdot 10^5$$$) — 将 $$$s_i$$$(专辑中第 $$$i$$$ 歌曲的名称)中字符串 $$$t$$$ 的出现次数作为连续子字符串进行计数, $$$t$$$ 仅由小写拉丁字母组成。
保证问题字符串$$$t$$$的总长度不超过$$$4 \cdot 10^5$$$。
输出
对于每个问题,打印一个整数 - 问题字符串 $$$t$$$ 在专辑第 $$$i$$$ 歌曲的名称中作为连续子字符串出现的次数。
示例
输入 #1
20 1 d 2 1 a 2 2 d 2 3 a 2 4 d 2 5 a 2 6 d 2 7 a 1 d 2 9 o 2 10 k 2 11 i 2 12 d 2 13 o 2 14 k 2 15 i 2 1 o 2 17 k 2 18 i 2 15 i 12 8 da 8 dada 8 ada 6 dada 3 dada 19 doki 19 ok 16 doki 15 doki 9 d 1 a 20 doki
输出 #1
4 3 3 2 0 1 1 2 1 1 0 2
注意
第一个示例的歌曲名称:
1.d
2. 达
3.爸爸
4.达达
5.爸爸
6.达达达
7. 爸爸
8.达达达
9.d
10. 做
11. 多克
12. doki
13. dokid
14. dokido
15. dokidok
16. dokidoki
17. 做
18. 多克
19. doki
20. dokidoki
因此每个问题字符串的出现次数是:
1. 字符串“da”从名称“dadadada”中的位置 $$$[1, 3, 5, 7]$$$ 开始;
2. 字符串“dada”从名称“dadadada”中的位置 $$$[1, 3, 5]$$$ 开始;
3. 字符串“ada”从名称“dadadada”中的位置 $$$[2, 4, 6]$$$ 开始;
4. 字符串“dada”从名称“dadada”中的位置 $$$[1, 3]$$$ 开始;
5. 名字“dad”中没有出现字符串“dada”;
6. 字符串“doki”从名称“doki”中的位置$$$[1]$$$开始;
7. 字符串“ok”从名称“doki”中的位置$$$[2]$$$开始;
8. 字符串“doki”从名称“dokidoki”中的位置 $$$[1, 5]$$$ 开始;
9. 字符串“doki”从名称“dokidok”中的位置 $$$[1]$$$ 开始;
10. 字符串“d”从名称“d”中的位置 $$$[1]$$$ 开始;
11. 名称“d”中没有出现字符串“a”;
12. 字符串“doki”从名称“dokidoki”中的位置 $$$[1, 5]$$$ 开始。