favorite We need a little bit of your help to keep things running, click on this banner to learn more

The Bank Cards

The Bank Cards

The bank "Kislovodsk" decided to introduce a new kind of bank cards. To do it, the identical blank cards were produced, that contains the special place for customer identification. Initially the code number X is written here. The bank has a special device that allows to erase some digits of X. The remaining numbers being recorded in a row, form a customer's account number. For example, if X = 12013456789, the account numbers 5, 12, 17 or 12013456789 can be obtained, but the numbers 22 or 71 impossible to obtain.

The distribution of account numbers in a bank is very simple. The accounts are assigned sequentially the numbers 1, 2, … Obviously, at some moment of the time there will appear the account number N that cannot be obtained from the digits of X with a way described above. The bank management wants to know the value of N.

Write a program that finds the value of N if X is given.


The positive integer X (1X < 101000) without leading zeroes.


Print number N without leading zeroes.

Time limit 1 second
Memory limit 64 MiB
Input example #1
Output example #1