Разом із непростою долею Надеко має рядок $s$, що складається з малих літер. Її заповітне бажання — побудувати рядок $t$, для якого виконуються такі умови:
- $t$ не містить $s$ як підпослідовність.
- Кожна підпослідовність рядка $s$, яка не збігається з $s$, міститься в $t$ як підпослідовність.
Допоможіть їй знайти рядок $t$ мінімально можливої довжини. Якщо таких рядків декілька, дозволяється вивести будь-який із них.
Вхідні дані
Єдиний рядок вхідних даних містить рядок $s$ ($2 \le |s| \le 10^6$) — рядок Надеко. Гарантується, що $s$ містить лише малі літери.
Вихідні дані
В одному рядку виведіть будь-який рядок $t$ мінімальної довжини, що задовольняє умови задачі.
Приклади
Вхідні дані 1
aaaa
Вихідні дані 1
aaa
Вхідні дані 2
bba
Вихідні дані 2
bab
Примітка
У другому прикладі рядок bab містить bb, ba, a, b як підпослідовності, але не містить bba. Також очевидно, що неможливо побудувати коректну послідовність довжини $2$, тому bab є можливою відповіддю.