Задачі
Підпослідовність
Підпослідовність
Дано рядок $s$. Вам потрібно знайти рядок мінімальної довжини, який не є підпослідовністю рядка $s$. Якщо таких рядків кілька, то знайдіть лексикографічно мінімальний. Можна отримати половину балів, якщо ви виведете рядок мінімальної довжини.
Нагадаємо, що рядок $a$ є підпослідовністю рядка $b$, якщо можна отримати $a$ з $b$, видаливши кілька (можливо, жоден або всі) символів.
Рядок $a$ лексикографічно менший рядка $b$ тоді і тільки тоді, коли виконується один з двох пунктів:
\begin{itemize}
\item $a$~--- префікс $b$, але $a \ne b$;
\item у першій позиції, де $a$ та $b$ відрізняються, у рядку $a$ знаходиться буква, яка зустрічається в алфавіті раніше, ніж відповідна буква у $b$.
\end{itemize}
\InputFile
Перший рядок містить рядок $s$ ($1 \leq |s| \leq 10^5$).
\OutputFile
Виведіть рядок.
\Note
Зверніть увагу, що у рядку присутні усі можливі символи, а також рядок починається та завершується на <<\t{a}>>.
Оскільки присутні усі можливі символи, то відповідь не може бути $1$. Оскільки після першої літери <<\t{a}>> є всі інші літери, то зрозуміло, що перший символ відповіді буде як мінімум <<\t{b}>>. Є підрядок <<\t{ba}>>, але немає <<\t{bb}>>, тому відповідь~--- <<\t{bb}>>.
Якби цей тест оцінювався, то ви отримали б $2$ бали, якби вивели <<\t{bb}>>. А якби ви вивели будь-який інший рядок довжини $2$ (наприклад, <<\t{aa}>>, <<\t{ba}>>, <<\t{zz}>>), то отримали б $1$ бал.
\Scoring
У цій задачі буде $50$ тестів, кожен з яких оцінюється у $2$ бали. Якщо ви виведете правильну відповідь у тесті, то ви отримаєте $2$ бали за нього.
Якщо ж рядок, який ви вивели, матиме таку ж довжину, що й відповідь, то ви отримаєте $1$ бал за нього. Цей рядок повинен містити лише малі літери англійського алфавіту. Зверніть увагу, що більше ніяких вимог до цього рядка немає. Тобто, ви можете навіть вивести рядок, який є підпослідовністю $s$. Головне, щоб довжина була такою ж, як і відповідь.
Вхідні дані #1
aqwertyuiopsdfghjklzxcvbnma
Вихідні дані #1
bb