Neben einem verdrehten Schicksal besitzt Nadeko eine Zeichenkette $s$, die aus Kleinbuchstaben besteht. Ihr größter Wunsch ist es, eine Zeichenkette $t$ zu konstruieren, für die folgende Bedingungen gelten:
- $t$ enthält $s$ nicht als Teilfolge.
- Jede Teilfolge von $s$, die nicht mit $s$ übereinstimmt, ist in $t$ als Teilfolge enthalten.
Hilf ihr, eine Zeichenkette $t$ von kleinstmöglicher Länge zu finden. Falls es mehrere solcher Zeichenketten gibt, darfst du eine beliebige davon ausgeben.
Eingabe
Eine einzige Zeile der Eingabe enthält die Zeichenkette $s$ ($2 \le |s| \le 10^6$) — Nadekos Zeichenkette. Es wird garantiert, dass $s$ nur aus Kleinbuchstaben besteht.
Ausgabe
Gib in einer einzigen Zeile eine beliebige Zeichenkette $t$ minimaler Länge aus, die die Bedingungen der Aufgabe erfüllt.
Beispiele
Eingabe 1
aaaa
Ausgabe 1
aaa
Eingabe 2
bba
Ausgabe 2
bab
Hinweis
Im zweiten Beispiel enthält die Zeichenkette bab zwar bb, ba, a, b als Teilfolgen, aber nicht bba. Es ist außerdem offensichtlich, dass es unmöglich ist, eine gültige Folge der Länge $2$ zu konstruieren, also ist bab eine mögliche Antwort.