4133: qko 吃串

全能 qko 的字符串也是学的相当好的，但学得更好的汪汪觉得他还有得加强，于是出了一个题来考他：
给定一个仅由小写字母构成的字符串 S ，定义 S[l, r] 为由 S[l], S[l +1] · · · S[r] 构成的 S 的子串 (1 ≤ l ≤ r ≤ |S|) ，给出 Q 次询问, 格式如下：
l r y 查询 y 在 S[l, r] 中出现的次数，y 是仅由小写字母构成的字符串。

第一行输入一个字符串 S (1 ≤ |S| ≤ 10⁵，其中 |S| 表示字符串 S 的长度) ；
第二行输入一个正整数 Q , 表示询问的次数 (1 ≤ Q ≤ 10⁵) ；
接下来 Q 行, 每行输入 l r y，表示询问的信息 (1 ≤ l ≤ r ≤ n, |y| ≤ 10⁵)；
题目保证 Q 次询问 |y| 的总和不超过 10⁵。

ababababa
2
1 7 aba
1 7 abc

3
0