题目描述

给定字符串 $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): 没有额外的限制。