Дано рядок s. Вам потрібно знайти рядок мінімальної довжини, який не є підпослідовністю рядка s. Якщо таких рядків кілька, то знайдіть лексикографічно мінімальний. Можна отримати половину балів, якщо ви виведете рядок мінімальної довжини.
Нагадаємо, що рядок a є підпослідовністю рядка b, якщо можна отримати a з b, видаливши кілька (можливо, жоден або всі) символів.
Рядок a лексикографічно менший рядка b тоді і тільки тоді, коли виконується один з двох пунктів:
a — префікс b, але a=b;
у першій позиції, де a та b відрізняються, у рядку a знаходиться буква, яка зустрічається в алфавіті раніше, ніж відповідна буква у b.
Перший рядок містить рядок s (1≤∣s∣≤105).
Виведіть рядок.
Зверніть увагу, що у рядку присутні усі можливі символи, а також рядок починається та завершується на «a
».
Оскільки присутні усі можливі символи, то відповідь не може бути 1. Оскільки після першої літери «a
» є всі інші літери, то зрозуміло, що перший символ відповіді буде як мінімум «b
». Є підрядок «ba
», але немає «bb
», тому відповідь — «bb
».
Якби цей тест оцінювався, то ви отримали б 2 бали, якби вивели «bb
». А якби ви вивели будь-який інший рядок довжини 2 (наприклад, «aa
», «ba
», «zz
»), то отримали б 1 бал.
У цій задачі буде 50 тестів, кожен з яких оцінюється у 2 бали. Якщо ви виведете правильну відповідь у тесті, то ви отримаєте 2 бали за нього.
Якщо ж рядок, який ви вивели, матиме таку ж довжину, що й відповідь, то ви отримаєте 1 бал за нього. Цей рядок повинен містити лише малі літери англійського алфавіту. Зверніть увагу, що більше ніяких вимог до цього рядка немає. Тобто, ви можете навіть вивести рядок, який є підпослідовністю s. Головне, щоб довжина була такою ж, як і відповідь.