P14855 [ICPC 2021 Yokohama R] Reversible Compression

Data compression is an essential technology in our information society. It is to encode a given string into a (preferably) more compact code string so that it can be stored and/or transferred efficiently. You are asked to design a novel compression algorithm such that even a code string is **reversed** it can be decoded into the given string. Currently, you are considering the following specification as a candidate. - A given string is a sequence of decimal digits, namely, $0, 1, 2, 3, 4, 5, 6, 7, 8,$ and $9$. - A code string is a sequence of code words, and a code word consists of two decimal digits $A$ and $L$. So, a code string is a sequence of even number of decimal digits. - A code string $A_1L_1 \cdots A_kL_k$ is decoded into a string by the following procedure. Here, for brevity, a decimal digit ($A_i$ or $L_i$) is also treated as the single digit decimal integer it represents. 1. $i \leftarrow 1$ 2. while ($i$ is not greater than $k$) { 3.  if ($A_i$ is zero) { output $L_i$ } 4.  else if ($L_i$ is zero) { do nothing } 5.  else if ($A_i$ is larger than the number of digits output so far) { raise an error } 6.  else { 7.    repeat $L_i$ times { 8.      output the $A_i$-th of the already output digits counted backwards 9.    } 10.  } 11.  $i \leftarrow i + 1$ 12. } For example, a code string $00125$ is decoded into a string $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 that the second digit in the already decoded digits, counted backwards, should be output. This should be repeated five times. For the first repetition, the decoded digits so far are $0$ and $1$, and thus the second last digit is $0$, which is output. For the second repetition, digits decoded so far are $0, 1,$ and $0$, and the second last is $1$, which is output. Repeating this three more times outputs $0, 1,$ and $0$. A sequence of code words that raises no error is a valid code string. A valid code string is said to be **reversible** when its reverse is also valid and both the original and its reverse are decoded into the same string. For example, the code string $00125$ is not reversible, because its reverse, $521000$, raises an error and thus is not valid. The code string $0010$ is not reversible though its reverse is valid. It is decoded into $0$, but its reverse $0100$ is decoded into $10$. On the other hand, $0015599100$ is reversible, because this and its reverse, $0019955100$, are both decoded into $0000000000000000$. You want to evaluate the performance of this compression method when applied to a variety of cases. Your task is to write a program that, for an arbitrary given digit string, finds the shortest reversible code string that is decoded into the given string.

The input consists of 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 is decoded into $s$. If there are multiple solutions with the same shortest length, output the earliest in the lexicographic order. Note that it is easily shown that a reversible code string always exists for any input string (e.g., see Sample Output 4).