Remove Duplicate Letters

Given a string s consisting of lowercase English letters, remove duplicate letters so that every letter appears exactly once and the resulting string is the smallest in lexicographical order.

In other words, if there exist multiple results that contain all the distinct letters of s, then return the one which is lexicographically smallest. The lexicographical comparison follows the standard order, i.e. for two strings \(a\) and \(b\), \(a < b\) if at the first position where they differ, the letter in \(a\) comes before the letter in \(b\) in the alphabet.

Example 1: Input: bcabc, Output: abc

Example 2: Input: cbacdcbc, Output: acdb

Note: The solution must process input from stdin and output the result to stdout.

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters.

You should read the input from stdin.

outputFormat

Output a single line containing the resulting string after removing duplicate letters such that each letter appears exactly once and the string is the smallest in lexicographical order.

The output should be written to stdout.

## sample

bcabc

abc