Along with a twisted fate, Nadeko has a string $s$ which consists of lowercase letters. Her ultimate wish is to construct a string $t$ for which the following conditions hold:
- $t$ does not contain $s$ as a subsequence.
- Every subsequence of $s$ which does not coincide with $s$ is contained in $t$ as a subsequence.
Help her find string $t$ of the minimal possible length. If there are multiple such strings, you are allowed to output any.
Input
A single line of the input contains string $s$ ($2 \le |s| \le 10^6$) — Nadeko's string. It is guaranteed that $s$ only contains lowercase letters.
Output
In the single line, output any string $t$ of minimal length which satisfies the conditions of the problem.
Examples
Input 1
aaaa
Output 1
aaa
Input 2
bba
Output 2
bab
Note
In the second example, string bab contains bb, ba, a, b as subsequences but does not contain bba. It is also obvious that it is impossible to construct a correct sequence of length $2$, so bab is a possible answer.