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:
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:
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?
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:
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:
It's guaranteed that the total length of question strings $$$t$$$ doesn't exceed $$$4 \cdot 10^5$$$.
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.
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
Song names of the first example:
Thus the occurrences for each question string are:
Name |
---|