CF1207G Indie Album
Description
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
N/A
Output Format
N/A
Explanation/Hint
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".