A device fingerprint is a string of lowercase English letters. Build a signature by deleting letters so that every distinct letter that appears in the original string appears exactly once in the result, and the result is the lexicographically smallest string achievable this way while keeping the remaining letters in their original relative order.
Because each distinct letter must appear exactly once, the signature's length equals the number of distinct letters in the string.
Input format
Line 1: a string of lowercase English letters.
Output format
A single line: the lexicographically smallest signature.
Constraints
- 1 <= length of the string <= 100000
- The string contains only lowercase English letters.