Підпослідовність

Дано рядок $s$. Вам потрібно знайти рядок мінімальної довжини, який не є підпослідовністю рядка $s$. Якщо таких рядків кілька, то знайдіть лексикографічно мінімальний. Можна отримати половину балів, якщо ви виведете рядок мінімальної довжини.

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

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

• $a$ — префікс $b$, але $a\ne b$;

• у першій позиції, де $a$ та $b$ відрізняються, у рядку $a$ знаходиться буква, яка зустрічається в алфавіті раніше, ніж відповідна буква у $b$.

Input

Перший рядок містить рядок $s$ ($1\le |s|\le 10^5$).

Output

Виведіть рядок.

Examples

Note

Зверніть увагу, що у рядку присутні усі можливі символи, а також рядок починається та завершується на «a».

Оскільки присутні усі можливі символи, то відповідь не може бути $1$. Оскільки після першої літери «a» є всі інші літери, то зрозуміло, що перший символ відповіді буде як мінімум «b». Є підрядок «ba», але немає «bb», тому відповідь — «bb».

Якби цей тест оцінювався, то ви отримали б $2$ бали, якби вивели «bb». А якби ви вивели будь-який інший рядок довжини $2$ (наприклад, «aa», «ba», «zz»), то отримали б $1$ бал.

Scoring

У цій задачі буде $50$ тестів, кожен з яких оцінюється у $2$ бали. Якщо ви виведете правильну відповідь у тесті, то ви отримаєте $2$ бали за нього.

Якщо ж рядок, який ви вивели, матиме таку ж довжину, що й відповідь, то ви отримаєте $1$ бал за нього. Цей рядок повинен містити лише малі літери англійського алфавіту. Зверніть увагу, що більше ніяких вимог до цього рядка немає. Тобто, ви можете навіть вивести рядок, який є підпослідовністю $s$. Головне, щоб довжина була такою ж, як і відповідь.