Indie Album
Contest: Educational Codeforces Round 71 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, dfs and similar, hashing, string suffix structures, strings, trees

Mishka's favourite experimental indie band has recently dropped a new album! Songs of that album share one gimmick. Each name $$$s_i$$$ is one of the following types:

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

Songs are numbered from $$$1$$$ to $$$n$$$. It's guaranteed that the first song is always of type $$$1$$$.

Vova is rather interested in the new album but he really doesn't have the time to listen to it entirely. Thus he asks Mishka some questions about it to determine if some song is worth listening to. Questions have the following format:

- $$$i~t$$$ — 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.

Mishka doesn't question the purpose of that information, yet he struggles to provide it. Can you please help Mishka answer all Vova's questions?

Input format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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".

Example 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

Example output:
4
3
3
2
0
1
1
2
1
1
0
2

Editorial:
There is a common approach for the problem "you are given a lot of strings and texts, count the number of occurences of the strings in the texts" — build an Aho-Corasick automaton on the given strings and somehow process the texts with it. Let's see if it can handle this problem.
The names of the songs can be represented as a tree. We may build an Aho-Corasick on the strings given in the queries, then try to input the names of the album into the automaton character-by-character with DFS on the aforementioned tree (feeding a character to the automaton when we enter a node, and reverting the automaton to the previous state when we leave that node). Suppose that when we are in the vertex corresponding to the $$$v$$$-th song, the automaton is in state $$$c$$$. If $$$c$$$ is a terminal state corresponding to some string from the queries, it means that the string from the query is a suffix of the $$$v$$$-th song. But some other strings can also be the suffixes of the same song — to find all such strings, we can start ascending from the state $$$c$$$ to the root of Aho-Corasick automaton using suffix links or dictionary links. Since suffix links can be represented as the edges of some rooted tree, then we can build some data structure on this tree that allows adding an integer to all vertices on the path from the root to the given vertex (for example, we can use Fenwick tree over Euler tour of the tree). Then, to check whether some string $$$t$$$ from the query is a suffix of the song $$$v$$$, we may add $$$1$$$ to all vertices on the path to state $$$c$$$, and then check the value in the state corresponding to $$$t$$$.
Okay, what about counting the occurences of $$$t$$$ in $$$v$$$? Let's consider the path from the root to $$$v$$$ in the "song tree". Every vertex on this path corresponds to some prefix of the song $$$v$$$, so we can add $$$1$$$ on the path to every state corresponding to some prefix, and then extract the answer from the state corresponding to $$$t$$$.
In fact, that's all we have to do to obtain a solution. Build an automaton on strings from queries, a tree of suffix links over this automaton, and a data structure on this tree; for each vertex of the song tree, store all queries to it. Then run a DFS on the song tree. When we enter some vertex, input the corresponding character into the automaton and add $$$1$$$ to all states from the root of suffix link tree to the current state; when we have to process queries to the current vertex, extract the values from the data structure; and when we leave a vertex, subtract $$$1$$$ from all states from the root of suffix link tree to the current state, and revert to the previous state.
This solution has complexity of $$$O(T \log T)$$$, where $$$T$$$ is the total length of all strings in the input.