Indie Album

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the number of songs in the album.

Each of the next $$$n$$$ lines contains the desciption of the $$$i$$$-th song of the album in the following format:

• $$$1~c$$$ — $$$s_i$$$ is a single lowercase Latin letter;
• $$$2~j~c$$$ — $$$s_i$$$ is the name $$$s_j$$$ ($$$1 \le j < i$$$) with a single lowercase Latin letter appended to its end.

The next line contains a single integer $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — the number of Vova's questions.

Each of the next $$$m$$$ lines contains the desciption of the $$$j$$$-th Vova's question in the following format:

• $$$i~t$$$ ($$$1 \le i \le n$$$, $$$1 \le |t| \le 4 \cdot 10^5$$$) — count the number of occurrences of string $$$t$$$ in $$$s_i$$$ (the name of the $$$i$$$-th song of the album) as a continuous substring, $$$t$$$ consists only of lowercase Latin letters.

It's guaranteed that the total length of question strings $$$t$$$ doesn't exceed $$$4 \cdot 10^5$$$.

Output:

For each question print a single integer — the number of occurrences of the question string $$$t$$$ in the name of the $$$i$$$-th song of the album as a continuous substring.

Sample Input:

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

Sample Output:

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

Note:

Song names of the first example:

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

Thus the occurrences for each question string are:

1. string "da" starts in positions $$$[1, 3, 5, 7]$$$ in the name "dadadada";
2. string "dada" starts in positions $$$[1, 3, 5]$$$ in the name "dadadada";
3. string "ada" starts in positions $$$[2, 4, 6]$$$ in the name "dadadada";
4. string "dada" starts in positions $$$[1, 3]$$$ in the name "dadada";
5. no occurrences of string "dada" in the name "dad";
6. string "doki" starts in position $$$[1]$$$ in the name "doki";
7. string "ok" starts in position $$$[2]$$$ in the name "doki";
8. string "doki" starts in positions $$$[1, 5]$$$ in the name "dokidoki";
9. string "doki" starts in position $$$[1]$$$ in the name "dokidok";
10. string "d" starts in position $$$[1]$$$ in the name "d";
11. no occurrences of string "a" in the name "d";
12. string "doki" starts in positions $$$[1, 5]$$$ in the name "dokidoki".