Reversible Compression

Data compression is an essential technology in our information society. It encodes a given string into a code string that is (preferably) more compact, so that the code can be stored and/or transferred efficiently.

You are asked to design a novel compression algorithm such that even when a code string is reversed, it can be decoded into the given string. The current candidate specification is as follows.

• A given string is a sequence of decimal digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
• A code string is a sequence of code words. A code word consists of two decimal digits A and L. So a code string is a sequence of an even number of decimal digits.
• A code string A$1$L$1$ $\cdots$ A$k$L$k$ is decoded into a string by the following procedure. For brevity, a decimal digit (A$i$ or L$i$) is also treated as the single-digit integer it represents.

i <- 1
while i <= k:
    if A_i is zero: output L_i
    else if L_i is zero: do nothing
    else if A_i is larger than the number of digits output so far: raise an error
    else: repeat L_i times: output the A_i-th of the already output digits, counted backwards
    i <- i + 1

For example, the code string 000125 is decoded into 0101010 as follows.

1. The first code word 00 outputs 0.
2. The second code word 01 outputs 1.
3. The first digit 2 of the last code word 25 means the second digit of the already decoded digits, counted backwards, is output. This is repeated five times. In the first repetition the decoded digits so far are 0 and 1, so the second-to-last digit 0 is output. In the second repetition the digits are 0, 1, and 0, so the second-to-last digit 1 is output. The next three repetitions output 0, 1, and 0.

A sequence of code words that raises no error is a valid code string. A valid code string is reversible when its reverse is also valid and both the original and its reverse are decoded into the same string.

For example, 000125 is not reversible, because its reverse, 521000, raises an error and so is not valid. 0010 is not reversible even though its reverse is valid: it decodes into 0, while its reverse 0100 decodes into 10. On the other hand, 0015599100 is reversible, because it and its reverse 0019955100 both decode into 00000000000000000.

You want to evaluate the performance of this compression method on a variety of cases. Write a program that, for an arbitrary given digit string, finds the shortest reversible code string that decodes into the given string.

The input is a single line containing a non-empty string $s$ of decimal digits. The length of $s$ does not exceed 500.

Output the shortest reversible code string that decodes into $s$. If several solutions have the same shortest length, output the one that is earliest in lexicographic order. A reversible code string always exists for any input string.