## DMOPC '20 Contest 5 P6 - Top Row

View as PDF

Points: 35 (partial)
Time limit: 4.0s
Java 8.0s
PyPy 3 8.0s
Memory limit: 512M
Java 1G
PyPy 3 1G

Author:
Problem types

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.

Of course, the game wants you to complete the rounds in the order which they are given (supposedly there is extra merit in doing so), so you will not be given the parameters and directly. Instead, you will be given and , and you may decrypt these values using the formula and , where represents the answer to the previous round and denotes the bitwise XOR operator. If there is no previous round, then .

#### Constraints

only contains lowercase characters.

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

#### 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 , representing the encrypted and values.

#### Output Specification

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

#### Sample Input

araaraoneesan
5
4 6
6 5
29 26
61 50
31 19

#### Sample Input (Unencrypted)

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

#### Sample Output

14
28
59
30
522

#### Explanation

For your convenience, an unencrypted version of the sample input is provided above.

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

1. Type a and press enter to submit in keystrokes.
2. Type ra and press enter to submit in keystrokes.
3. Type ara and press enter to submit in keystrokes.
4. Type r and press enter to submit in keystrokes.
5. 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.