En plus d'un destin tourmenté, Nadeko possède une chaîne de caractères $s$ composée de lettres minuscules. Son souhait ultime est de construire une chaîne $t$ vérifiant les conditions suivantes :
- $t$ ne contient pas $s$ comme sous-séquence.
- Toute sous-séquence de $s$ qui ne coïncide pas avec $s$ est contenue dans $t$ comme sous-séquence.
Aidez-la à trouver une chaîne $t$ de longueur minimale possible. S'il existe plusieurs chaînes de ce type, vous pouvez en afficher une quelconque.
Entrée
Une seule ligne de l'entrée contient la chaîne $s$ ($2 \le |s| \le 10^6$) — la chaîne de Nadeko. Il est garanti que $s$ ne contient que des lettres minuscules.
Sortie
Sur une seule ligne, affichez n'importe quelle chaîne $t$ de longueur minimale qui satisfait les conditions du problème.
Exemples
Entrée 1
aaaa
Sortie 1
aaa
Entrée 2
bba
Sortie 2
bab
Remarque
Dans le deuxième exemple, la chaîne bab contient bb, ba, a, b comme sous-séquences mais ne contient pas bba. Il est également évident qu'il est impossible de construire une séquence valide de longueur $2$, donc bab est une réponse possible.