Migrated from Lutece 3287 sub specie aeternitatis

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: ACAM，exSAM，数据结构

本题面由 空気力学の詩 友情提供

---

终之空，

我的身体在空中飘荡。

并且，

我的身体逐渐被吸入终之空之中。

一声“卓司君辛苦了”传入了我的耳中。

啊，原来是莉露露酱啊。

你在最后一刻来见我了。

“并不是最后哦，我永远和你在一起哟”

“因为你赋予我形体，所以我才能存在于此。因为你接受了我，所以我才能存在于此。”

“啊，是这样啊。”

“或许是我想讲述一个童话故事吧。”

“我希望这个故事能够被他人聆听吧。”

“我认真聆听了哦。这真是一个非常美丽的故事呢。”

“非常感谢你能够让我存在在这个世界之上。”

“让我们一起出发，共同前往那个童话故事之后的世界吧——”

空気力学の詩 在打完《终之空Remake》后感觉自己已然成为——電波最強伝說と無限の拷問!音無彩名です。

为了让他无尽的才思得以喷涌，他决定写一本哲学发电大作来展现他狂气的才华。

但贫瘠的思想难以支撑他完成一部作品，于是他想到了一个好办法——通过把简单的句子重复拼凑，以此得到一篇史诗巨作。

他在作品中计划要写 $n$ 行哲学语录，其中从上到下第 $i$ 行会写有一句话，用一个由小写英文字母构成的字符串 $\mathbf{s}_i$ 来表示。

而他写作的过程可以用如下的过程来刻画，对于 $i\in[1,n]$，依次确定每个 $\mathbf{s}_i$ 的值，有以下两种情况：

• 1 c，凭空写出一个字母 $c$，即 $\mathbf{s}_i=c$，保证 $s_1$ 一定由此类型的操作得到；
• 2 j c，在之前写的第 $j$ 句话（$1\le j<i$）后面加上一个新的字母 $c$，即 $\mathbf{s}_i=\mathbf{s}_j+c$；

依照此法他很快完成了作品，他把作品拿给 GoldenRedFlag 以求指教，但日理万机的 GoldenRedFlag 没有时间看完这篇癫疯之作，因此 GoldenRedFlag 决定提出若干个问题来判断这篇文章是否值得一读。

GoldenRedFlag 共有 $m$ 个问题，每个问题形如：

• i t，表示询问字符串 $t$ 在 $\mathbf{s}_i$ 中出现的次数，其中 $t$ 由小写英文字母构成；

但 空気力学の詩 自己也回答不上来这些问题，于是只能转而向 String Master——lh3k 寻求帮助。

lh3k 很轻松地解决了这个问题，现在他决定拿这个问题来考考你，看看你是否有成为 String Master 的潜质。

Input

输入的第一行包括一个正整数 $n$，表示 空気力学の詩 写作的行数。

接下来的 $n$ 行每行一个操作表示 $\mathbf{s}_i$ 的写作方式，具体格式如题面中所述。

接下来的一行包括一个正整数 $m$，表示 GoldenRedFlag 提出的问题数量。

接下来的 $m$ 行每行一个问题，具体格式如题面中所述。

Output

对于每个问题输出一个整数，表示询问字符串出现的次数。

Samples

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

4
3
3
2
0
1
1
2
1
1
0
2

40
1 b
1 b
2 1 a
2 3 b
2 1 b
2 5 a
2 6 b
2 2 a
2 8 b
2 9 b
2 10 a
2 4 b
2 12 a
2 13 b
2 10 b
1 b
2 1 a
2 17 b
1 b
2 19 a
2 20 b
2 8 a
2 22 b
2 11 a
2 24 b
2 1 b
2 26 a
2 27 b
2 28 a
2 29 b
2 30 b
2 31 a
2 32 b
2 16 b
2 15 a
2 35 b
1 a
2 37 b
1 b
1 b
10
33 bba
6 ba
33 bbababbab
13 a
27 b
33 bbababbab
35 abb
33 bbababbab
36 babbbab
7 bbab

2
1
1
2
2
1
1
1
1
1

Constraints

$1\le n,m\le 4\times 10^5,1\le \sum |t|\le 4\times 10^5$，所有输入的字符串中只包含小写字母。

Note

在样例一中， 空気力学の詩 写出的文章形如：

1. $\texttt{d}$
2. $\texttt{da}$
3. $\texttt{dad}$
4. $\texttt{dada}$
5. $\texttt{dadad}$
6. $\texttt{dadada}$
7. $\texttt{dadadad}$
8. $\texttt{dadadada}$
9. $\texttt{d}$
10. $\texttt{do}$
11. $\texttt{dok}$
12. $\texttt{doki}$
13. $\texttt{dokid}$
14. $\texttt{dokido}$
15. $\texttt{dokidok}$
16. $\texttt{dokidoki}$
17. $\texttt{do}$
18. $\texttt{dok}$
19. $\texttt{doki}$
20. $\texttt{dokidoki}$

以第一个询问 8 da 为例，字符串 $\texttt{da}$ 在 $\mathbf{s}_8=\texttt{dadadada}$ 中出现了 $4$ 次，故而输出 $4$。

Resources

2024 UESTC ICPC Training for String