Problem Description

Given a string $S$ of length $n$ consisting only of lowercase letters, there are $m$ queries. Each query asks how many essentially different non-empty substrings are contained in the string formed by the $L$-th to the $R$-th characters of $S$.

Two strings $a, b$ are defined to be the same if and only if $|a|=|b|$ and for all $i\in[1,|a|]$, we have $a_i=b_i$.

Input Format

The first line contains a string $S$ of length $n$.

The second line contains an integer $m$, indicating the number of queries.

The next $m$ lines each contain two integers $l_i, r_i$, describing the $i$-th query.

Output Format

Output $m$ lines, each containing an integer, representing the answer to the $i$-th query.

aababc
3
1 2
2 4
3 6

2
5
9

Hint

Explanation for Sample 1

• For the first query, the string is $\texttt{aa}$, and it contains $\texttt{a}$ and $\texttt{aa}$, for a total of $2$ essentially different substrings.
• For the second query, the string is $\texttt{aba}$, and it contains $\texttt{a},\texttt{b},\texttt{ab},\texttt{ba},\texttt{aba}$, for a total of $5$ essentially different substrings.
• For the third query, the string is $\texttt{babc}$, and it contains $\texttt{a}$,$\texttt{b}$,$\texttt{c}$,$\texttt{ab}$,$\texttt{ba}$,$\texttt{bc}$,$\texttt{bab}$,$\texttt{abc}$,$\texttt{babc}$, for a total of $9$ essentially different substrings.

Constraints

• For $20\%$ of the testdata, $n\leq 3\times 10^3$ and $m\leq 3\times 10^3$.
• For $100\%$ of the testdata, $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])$.

Translated by ChatGPT 5