Archiver#5238
Vasya is on a mission to revolutionize the market with his innovative text compression technique for sequences of lowercase Latin letters. His method involves encoding text as a series of commands, which come in two types:
c: Append the character c to the current line.
i k: Append characters to the current line sequentially. The first character appended corresponds to the -th character of the current line, the second to the (i+1)-th character, and so forth, with the -th character matching the (i+k-1)-th character. It is guaranteed that will not exceed the current length of the line.
For instance, the command sequence a, b, 1 3 results in the string ababa, and the sequence a, 1 3, b, 3 3 results in the string aaaabaab.
The storage requirement for a command of the first type is byte, while a command of the second type requires bytes. Vasya can reconstruct the original text from these commands but cannot reverse the process. Your task is to assist Vasya in optimizing the storage of the given string using the least number of bytes possible.
The input consists of a string composed of lowercase Latin letters, with a maximum length of characters.
On the first line of the output, print the total number of bytes required to store the sequence of commands, followed by the number of commands in the sequence. In the subsequent lines, list each command on a new line. For a command of the first type, simply print the letter. For a command of the second type, print two numbers: the starting position of the character in the string (with positions starting at one) from which copying begins, and the number of characters to copy.
Example 1