题目描述
给定字符串 $S$，$q$ 次询问，每次给出 $l,r(1 \leq l \leq r \leq |S|)$，你需要求出 $S[l:r]$ 本质不同的子串数量。
输入格式
输入的第一行包含一个字符串 $S$。
接下来一行包含一个整数 $q$。
接下来 $q$ 行，每行两个整数 $l,r$，描述一组询问。
输出格式
输出 $q$ 行，每行一个整数，表示答案。
样例数据
样例 1 输入
helloeveryonenationalolympiadininformaticswilltakeplaceinaugustgoodlucktoeveryonebythewaythisisejudgecontestadministrationsystem
5
1 58
18 46
35 57
25 40
55 56样例 1 输出
1662
420
267
129
3样例 2 输入
browseprivatelyexplorefreelydefendyourselfagainsttrackingandsurveillancecircumventcensorship
5
1 30
15 45
20 60
30 70
40 80样例 2 输出
447
476
830
832
832样例 3
见下发文件
子任务
对于所有数据，$1 \leq |S| \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5$。
- Subtask 1(5 Points): $|S|,q \leq 50$
- Subtask 2(20 Points): $q \leq 50$
- Subtask 3(26 Points): $S$ 中只含有
a、b - Subtask 4(23 Points): $|S| \leq 2 \times 10^4, q \leq 4 \times 10^4$
- Subtask 5(26 Points): 没有额外的限制。