题目描述

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$
3. }

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).

00000000000000000

0015599100

0101010 

000122221000

123123123123123123123123123123

01020336699993302010

123456789

010203040506070809908070605040302010