The Bank Cards#1778

The Bank Cards

1 second

64 megabytes

Easy

The bank "Westville" is introducing a new type of bank card. For this, identical blank cards are produced, each with a special place for customer identification. Initially, the code number $X$ is written in this place. The bank has a special device that allows some digits of $X$ to be erased. The remaining digits, when written in order, form a customer's account number. For example, if $X = 12013456789$ X = 12013456789, account numbers $5$ , $12$ , $17$ , or $12013456789$ can be obtained, while numbers $22$ or $71$ cannot.

Account numbers in the bank are assigned sequentially: $1$ , $2$ , $\dots$ . It is clear that with this method, at some point there will be an account number $N$ that cannot be obtained from the digits of $X$ in the manner described above. The bank management wants to know the value of $N$ .

Write a program to find $N$ for the given $X$ .

Input

The positive integer $X$ ( $1 \leq X < 1 0^{1000}$ 1 \leq X < 10^{1000}) without leading zeroes.

Output

Print the value of $N$ without leading zeroes.

Examples

Example 1

Loading

X = 12013456789

1 \leq X < 1 0^{1000}