区间本质不同子串个数

给定一个长度为 $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$ 次询问的答案。

aababc
3
1 2
2 4
3 6

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])$。