Smallest Lexicographic Order

You are given a string representing the current arrangement of books on a shelf. Each character in the string represents a unique book. The allowed operation is to move a book (character) to the front of the shelf, but each book can only be moved once. Your task is to determine the lexicographically smallest arrangement that can be achieved by applying these operations.

Operation Constraint: Each book (character) can be moved to the front at most once.

Formally, if the original arrangement is given by a string \( s \) of length \( n \), you must produce a string \( t \) (a subsequence of \( s \)) such that:

[ t = s_{i_1}s_{i_2}\ldots s_{i_k}, \quad (1 \leq i_1 < i_2 < \ldots < i_k \leq n) ]

and \( t \) is the smallest lexicographic string satisfying the condition that each character appears at most once, and you are allowed to bring a character to the front only if it has not been moved before.

For example, given the input cbacdcbc, the lexicographically smallest arrangement is acdb.

inputFormat

The input consists of a single line containing a non-empty string which represents the initial arrangement of books.

Input is given via standard input (stdin).

outputFormat

Output the lexicographically smallest arrangement (a string) that can be obtained by performing the allowed operations. The output should be printed to standard output (stdout).

## sample

cbacdcbc

acdb