Note: This problem is an offline version of the original problem from DMOPC. The only difference is that and 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 of lowercase characters. Every game is split into rounds. In the round integers and are given, and your task is to type out all of the distinct non-empty substrings of the substring of from index to 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 from index to once. Since you still strive to be as fast as possible, please compute the minimum number of keystrokes needed to complete each round.
Constraints
only contains lowercase characters.
Subtask 1 [5%]
Subtask 2 [15%]
Subtask 3 [30%]
All characters of 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 .
The second line contains the integer , the number of rounds.
The next lines each contain integers and .
Output Specification
Output 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 from index to , which is ara
. One possible strategy is as follows:
- Type
a
and press enter to submit in keystrokes. - Type
ra
and press enter to submit in keystrokes. - Type
ara
and press enter to submit in keystrokes. - Type
r
and press enter to submit in keystrokes. - Type
ar
and press enter to submit in keystrokes.
Thus, this round was completed with 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.
Comments