Lexicographically Smallest Subsequence

You are given a string s consisting of lowercase English letters. Your task is to find the lexicographically smallest subsequence of s that contains every character that appears in s at most once while preserving the order of characters.

A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements.

For example, if s = "ababc", one valid subsequence that contains each distinct character once is "abc" and it is the lexicographically smallest possible.

Note: A string a is lexicographically smaller than a string b if at the first position where they differ, the character in a comes before the corresponding character in b in alphabetical order.

inputFormat

The input is provided via standard input (stdin) and contains a single line with a non-empty string s consisting of lowercase English letters.

For example:

aabcbc

outputFormat

Output the lexicographically smallest subsequence of s (via standard output, stdout) that contains each character at most once and retains the relative order.

For example:

abc

## sample

ababc

abc