Smallest Subsequence of Distinct Characters

Given a string \( s \) consisting of lowercase English letters, your task is to find the smallest subsequence of \( s \) that contains every distinct character present in \( s \) exactly once. In other words, you need to remove duplicate occurrences of characters from \( s \) and rearrange the remaining characters (if necessary) such that the resulting string is the smallest in lexicographical order among all possible subsequences that contain all unique characters.

The problem can be formally defined as follows:

Let \( s \) be a string of length \( n \) and let \( U \) be the set of unique characters in \( s \). Find a sequence \( t \) such that:

• \( t \) is a subsequence of \( s \).
• The set of characters in \( t \) is exactly \( U \).
• Among all such subsequences, \( t \) is the smallest in lexicographical order.

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

For example:

• \( s = \texttt{abcabc} \) results in \( t = \texttt{abc} \).
• \( s = \texttt{cbacdcbc} \) results in \( t = \texttt{acdb} \).
• \( s = \texttt{bbcaac} \) results in \( t = \texttt{bac} \).

inputFormat

The input consists of a single line containing a non-empty string \( s \) composed of lowercase English letters only. The string \( s \) may also be empty in some test cases.

outputFormat

Output the smallest subsequence (as described above) as a single string on a single line. The result should include every distinct character from the input exactly once and should be lexicographically minimal.

## sample

abcabc

abc