Подпоследовательность

Дана строка $s$. Ваша задача — найти строку минимальной длины, которая не является подпоследовательностью строки $s$. Если таких строк несколько, выберите лексикографически минимальную. Вы можете получить половину баллов, если найдете строку минимальной длины.

Напомним, что строка $a$ является подпоследовательностью строки $b$, если $a$ можно получить из $b$, удалив несколько (возможно, ни одного или все) символов.

Строка $a$ лексикографически меньше строки $b$, если выполняется одно из следующих условий:

• $a$ является префиксом $b$, но $a\ne b$;

• в первой позиции, где $a$ и $b$ отличаются, буква в $a$ стоит раньше в алфавите, чем соответствующая буква в $b$.

Входные данные

Первая строка содержит строку $s$ ($1\le |s|\le 10^5$).

Выходные данные

Выведите строку.

Примеры

Примечание

Обратите внимание, что в строке присутствуют все возможные символы, и строка начинается и заканчивается на «a».

Поскольку присутствуют все возможные символы, ответ не может быть длины $1$. Так как после первой буквы «a» есть все другие буквы, ясно, что первый символ ответа будет как минимум «b». Подстрока «ba» существует, но «bb» нет, поэтому ответ — «bb».

Если бы этот тест оценивался, вы получили бы $2$ балла за вывод «bb». Если бы вы вывели любую другую строку длины $2$ (например, «aa», «ba», «zz»), вы получили бы $1$ балл.

Оценивание

В этой задаче будет $50$ тестов, каждый из которых оценивается в $2$ балла. Если вы выведете правильный ответ в тесте, вы получите $2$ балла за него.

Если строка, которую вы выведете, будет иметь такую же длину, как и правильный ответ, вы получите $1$ балл за этот тест. Эта строка должна содержать только строчные буквы английского алфавита. Обратите внимание, что больше никаких требований к этой строке нет. То есть, вы можете даже вывести строку, которая является подпоследовательностью $s$. Главное, чтобы длина была такой же, как у ответа.