Любимая экспериментальная инди группа Мишки недавно выпустила новый альбом! У песен этого альбома есть одна общая особенность. Название каждой песни \(s_i\) — одно из следующих типов:
- \(1~c\) — одна строчная латинская буква;
- \(2~j~c\) — название \(s_j\) (\(1 \le j < i\)) с приписанной к нему справа одной строчной латинской буквой.
Песни пронумерованы от \(1\) до \(n\). Гарантируется, что первая песня всегда типа \(1\).
Вове тоже интересен новый альбом, но он никак не может найти время его послушать целиком. Поэтому он решил задать Мишке несколько вопросов о нем, чтобы узнать, достойна ли какая-нибудь песня прослушивания. Все вопросы имеют одинаковый формат:
- \(i~t\) — посчитать количество вхождений строки \(t\) в \(s_i\) (название \(i\)-й песни альбома), как подстроки, \(t\) состоит только из строчных латинских букв.
И хотя Мишка не понимает, какая польза от этой информации, он старается помочь Вове. Однако вопросов так много, что он не справляется. Помогите, пожалуйста, Мише ответить на все вопросы Вовы.
Выходные данные
На каждый вопрос выведите одно целое число — количество вхождений строки вопроса \(t\) в название \(i\)-й песни альбома, как подстроки.
Примечание
Названия песен из первого примера:
- d
- da
- dad
- dada
- dadad
- dadada
- dadadad
- dadadada
- d
- do
- dok
- doki
- dokid
- dokido
- dokidok
- dokidoki
- do
- dok
- doki
- dokidoki
Тогда вхождения для каждого вопроса следующие:
- строка «da» начинается в позициях \([1, 3, 5, 7]\) в названии «dadadada»;
- строка «dada» начинается в позициях \([1, 3, 5]\) в названии «dadadada»;
- строка «ada» начинается в позициях \([2, 4, 6]\) в названии «dadadada»;
- строка «dada» начинается в позициях \([1, 3]\) в названии «dadada»;
- нет вхождений строки «dada» в названии «dad»;
- строка «doki» начинается в позиции \([1]\) в названии «doki»;
- строка «ok» начинается в позиции \([2]\) в названии «doki»;
- строка «doki» начинается в позициях \([1, 5]\) в названии «dokidoki»;
- строка «doki» начинается в позиции \([1]\) в названии «dokidok»;
- строка «d» начинается в позиции \([1]\) в названии «d»;
- нет вхождений строки «a» в названии «d»;
- строка «doki» начинается в позициях \([1, 5]\) в названии «dokidoki».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|