Lexicographically Smallest Unique Subsequence

Given a string s, your task is to produce the lexicographically smallest string that contains only unique characters while preserving the relative order of their first appearance in s. In other words, remove duplicate letters such that the resulting string is the smallest possible in lexicographical order while maintaining the original order of first occurrences.

Note: The input string consists of lowercase English letters only.

Examples:

• If s = "cbacdcbc", the output should be acdb.
• If s = "bcabc", the output should be abc.
• If s = "aabbcc", the output should be abc.

inputFormat

The input consists of a single line containing a string s (1 ≤ |s| ≤ 10⁴), where s is composed only of lowercase English letters.

outputFormat

Output the lexicographically smallest string consisting of unique characters while preserving the relative order of their first appearance in s.

cbacdcbc

acdb