Note: This problem is an offline version of the original problem from DMOPC. The only difference is that $l_i$ and $r_i$ are not encrypted, and will be given explicitly in the input files. Please note the adjusted time and memory limits.

After several weeks of training, you've finally managed to increase your typing speed to a staggering 40 WPM. Accordingly, you've also found another modified version of TypeRacer to intensify your training. In this game, you start off with a string $S$ of lowercase characters. Every game is split into $Q$ rounds. In the $i^{\text{th}}$ round $2$ integers $l_i$ and $r_i$ are given, and your task is to type out all of the distinct non-empty substrings of the substring of $S$ from index $l_i$ to $r_i$ once.

To do this, you are provided with an empty screen at the start of the round. In one keystroke, you may add a lowercase character to the end of the current string on the screen, or you may press enter to submit the current string on the screen, simultaneously clearing the screen of all characters. The round is completed when you have submitted every distinct non-empty substring of the substring of $S$ from index $l_i$ to $r_i$ once. Since you still strive to be as fast as possible, please compute the minimum number of keystrokes needed to complete each round.

Constraints

$1\le |S|\le {10}^5$

$1\le Q\le 5\times {10}^5$

$1\le l_i\le r_i\le |S|$

$S$ only contains lowercase characters.

Subtask 1 [5%]

$1\le |S|,Q\le 400$

Subtask 2 [15%]

$\sum _{i=1}^Q(r_i-l_i)\le {10}^6$

Subtask 3 [30%]

All characters of $S$ are chosen independently and uniformly at random from the set of lowercase characters.

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains the string $S$.

The second line contains the integer $Q$, the number of rounds.

The next $Q$ lines each contain $2$ integers $l_i$ and $r_i$.

Output Specification

Output $Q$ lines, each containing the minimum number of keystrokes needed to complete the corresponding round.

Sample Input

araaraoneesan
5
4 6
8 11
1 6
6 9
1 13

Sample Output

14
28
59
30
522

Explanation

The first round is played on the substring of $S$ from index $4$ to $6$, which is ara. One possible strategy is as follows:

1. Type a and press enter to submit in $2$ keystrokes.
2. Type ra and press enter to submit in $3$ keystrokes.
3. Type ara and press enter to submit in $4$ keystrokes.
4. Type r and press enter to submit in $2$ keystrokes.
5. Type ar and press enter to submit in $3$ keystrokes.

Thus, this round was completed with $2+3+4+2+3=14$ keystrokes in total, and it can be shown that this is the minimum number of keystrokes possible. Note that you do not have to submit a twice, since every distinct substring only needs to be submitted once.