406091: GYM102263 M Two Operations

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Two Operationstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ayoub has a string $$$S$$$ consists of only lower case Latin letters, and he wants you to make some operations on it:

  1. you can swap any two characters in the string.
  2. you can delete any two adjacent characters that have the same value and replace them with the next character alphabetically,for example string $$$"abbx"$$$ could be $$$"acx"$$$ after one operation, string $$$"zz"$$$ could not be changed; because z is the last character in the English alphabets.

Ayoub wants you to make the string lexicographically maximal using the mentioned operations as many times as you want, can you help him?

String $$$x = x_1x_2... x_{|x|}$$$ is lexicographically larger than string $$$y = y_1y_2... y_{|y|}$$$, if either $$$|x| > |y|$$$ and $$$x_1 = y_1, x_2 = y_2, ... , x_{|y|}= y_{|y|}$$$, or exists such number $$$r (r < |x|, r < |y|)$$$, that $$$x_1 = y_1, x_2 = y_2, ... , x_r = y_r$$$ and $$$x_r + 1 > y_r + 1$$$. Characters in lines are compared like their ASCII codes.

Input

The input contains a single string $$$S$$$ $$$(1 \leq |S| \leq 10^5)$$$.

It is guaranteed that string $$$S$$$ consists of only lower case Latin letters.

Output

print the lexicographically maximal string that could be obtained using these two operations.

ExamplesInput
abbx
Output
xca
Input
zyayz
Output
zzza
Note

In the first test case Ayoub replaced $$$"bb"$$$ with $$$"c"$$$ so the string has been changed to $$$"acx"$$$, then he swapped 'a' with 'x' so the result is $$$"xca"$$$ and it is the lexicographically maximal string.

Source/Category

加入题单

算法标签: