题目描述

给定一个长度为 $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])$。