G. Инди альбом
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Любимая экспериментальная инди группа Мишки недавно выпустила новый альбом! У песен этого альбома есть одна общая особенность. Название каждой песни $$$s_i$$$ — одно из следующих типов:

  • $$$1~c$$$ — одна строчная латинская буква;
  • $$$2~j~c$$$ — название $$$s_j$$$ ($$$1 \le j < i$$$) с приписанной к нему справа одной строчной латинской буквой.

Песни пронумерованы от $$$1$$$ до $$$n$$$. Гарантируется, что первая песня всегда типа $$$1$$$.

Вове тоже интересен новый альбом, но он никак не может найти время его послушать целиком. Поэтому он решил задать Мишке несколько вопросов о нем, чтобы узнать, достойна ли какая-нибудь песня прослушивания. Все вопросы имеют одинаковый формат:

  • $$$i~t$$$ — посчитать количество вхождений строки $$$t$$$ в $$$s_i$$$ (название $$$i$$$-й песни альбома), как подстроки, $$$t$$$ состоит только из строчных латинских букв.

И хотя Мишка не понимает, какая польза от этой информации, он старается помочь Вове. Однако вопросов так много, что он не справляется. Помогите, пожалуйста, Мише ответить на все вопросы Вовы.

Входные данные

В первой строке записано одно целое число $$$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$$$) — количество вопросов Вовы.

В каждой из следующих $$$m$$$ строк записан $$$j$$$-й вопрос Вовы в следующем формате:

  • $$$i~t$$$ ($$$1 \le i \le n$$$, $$$1 \le |t| \le 4 \cdot 10^5$$$) — посчитать количество вхождений строки $$$t$$$ в $$$s_i$$$ (название $$$i$$$-й песни альбома), как подстроки, $$$t$$$ состоит только из строчных латинских букв.

Гарантируется, что суммарная длина всех строк $$$t$$$ из вопросов не превосходит $$$4 \cdot 10^5$$$.

Выходные данные

На каждый вопрос выведите одно целое число — количество вхождений строки вопроса $$$t$$$ в название $$$i$$$-й песни альбома, как подстроки.

Пример
Входные данные
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
Примечание

Названия песен из первого примера:

  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

Тогда вхождения для каждого вопроса следующие:

  1. строка «da» начинается в позициях $$$[1, 3, 5, 7]$$$ в названии «dadadada»;
  2. строка «dada» начинается в позициях $$$[1, 3, 5]$$$ в названии «dadadada»;
  3. строка «ada» начинается в позициях $$$[2, 4, 6]$$$ в названии «dadadada»;
  4. строка «dada» начинается в позициях $$$[1, 3]$$$ в названии «dadada»;
  5. нет вхождений строки «dada» в названии «dad»;
  6. строка «doki» начинается в позиции $$$[1]$$$ в названии «doki»;
  7. строка «ok» начинается в позиции $$$[2]$$$ в названии «doki»;
  8. строка «doki» начинается в позициях $$$[1, 5]$$$ в названии «dokidoki»;
  9. строка «doki» начинается в позиции $$$[1]$$$ в названии «dokidok»;
  10. строка «d» начинается в позиции $$$[1]$$$ в названии «d»;
  11. нет вхождений строки «a» в названии «d»;
  12. строка «doki» начинается в позициях $$$[1, 5]$$$ в названии «dokidoki».