区间本质不同子串个数

题目描述

给定一个长度为 $n$ 的字符串 $S$,$m$ 次询问由 $S$ 的第 $L$ 到第 $R$ 个字符组成的字符串包含多少个本质不同的子串。 定义两个字符串 $a,b$ 相同当且仅当 $|a|=|b|$ 并且对于 $i\in[1,|a|]$ 都有 $a_i=b_i$。

输入输出格式

输入格式


第一行一个长度为 $n$ 的字符串 $S$。 第二行一个整数 $m$,表示询问次数。 接下来 $m$ 行,第 $i$ 行包含两个整数 $l_i,r_i$,描述第 $i$ 次询问。

输出格式


$m$ 行,每行一个整数,表示第 $i$ 次询问的答案。

输入输出样例

输入样例 #1

aababc
3
1 2
2 4
3 6

输出样例 #1

2
5
9

说明

#### 样例 1 解释 - 第一次询问,字符串为 $\texttt{aa}$,包含 $\texttt{a}$,$\texttt{aa}$ 共 $2$ 种本质不同子串。 - 第二次询问,字符串为 $\texttt{aba}$,包含 $\texttt{a},\texttt{b},\texttt{ab},\texttt{ba},\texttt{aba}$, 共 $5$ 种本质不同子串。 - 第三次询问,字符串为 $\texttt{babc}$,包含 $\texttt{a}$,$\texttt{b}$,$\texttt{c}$,$\texttt{ab}$,$\texttt{ba}$,$\texttt{bc}$,$\texttt{bab}$,$\texttt{abc}$,$\texttt{babc}$ 共 $9$ 种本质不同子串。 #### 数据规模与约定 - 对于 $20\%$ 的数据,满足 $n\leq 3\times 10^3$,$m\leq 3\times 10^3$。 - 对于 $100\%$ 的数据,满足 $1\leq n\leq 10^5$,$1\leq m\leq 2\times 10^5$,$1\leq l_i\leq r_i\leq n(i\in[1,m])$。