G. Lexicographically Maximum
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ consisting of lowercase English letters.

You can do the following operation on $$$s$$$:

— Choose some substring $$$s[l \dots r]$$$, and let $$$x$$$ be the number of distinct characters in $$$s[l \dots r]$$$.

— Change all characters in $$$s[l \dots r]$$$ to the $$$x$$$-th character in the alphabet (e.g., the first character is 'a', the second is 'b', and so on).

You apply the above operation any number of times (possibly zero) such that $$$\textbf{no index gets changed more than once}$$$.

What is the lexicographically maximum string that could be obtained?

Input

The first and only line of the input contains a string $$$s$$$ consisting of lowercase English letters ($$$1 \le |s| \le 10^6$$$).

Output

The lexicographically maximum string that could be obtained.

Examples
Input
ab
Output
bb
Input
adbbab
Output
cccccc
Input
adbad
Output
ccccd