Subsequence

Given a string $s$, your task is to find the shortest string that is not a subsequence of $s$. If there are multiple such strings, choose the lexicographically smallest one. You can earn partial credit by outputting a string of the minimum length.

Recall that a string $a$ is a subsequence of a string $b$ if $a$ can be derived from $b$ by deleting some (possibly none or all) characters.

A string $a$ is considered lexicographically smaller than a string $b$ if one of the following conditions holds:

• $a$ is a prefix of $b$, but $a\ne b$;

• At the first position where $a$ and $b$ differ, the character in $a$ precedes the character in $b$ in the alphabet.

Input

The first line contains the string $s$ ($1\le |s|\le 10^5$).

Output

Output the required string.

Examples

Note

Note that all possible characters are present in the string, and the string starts and ends with "a".

Since all possible characters are present, the answer cannot be of length $1$. Given that after the first letter "a", all other letters are present, it is evident that the first character of the answer must be at least "b". There is a substring "ba", but not "bb", so the answer is "bb".

If this test were scored, you would receive $2$ points for outputting "bb". If you output any other string of length $2$ (for example, "aa", "ba", "zz"), you would receive $1$ point.

Scoring

This problem consists of $50$ tests, each worth $2$ points. If you provide the correct answer for a test, you will earn $2$ points for it.

If the string you output has the same length as the correct answer, you will receive $1$ point for it. This string must consist only of lowercase English letters. Note that there are no other requirements for this string. You can even output a string that is a subsequence of $s$, as long as its length matches the answer.