Wraz z pokręconym losem Nadeko ma napis $s$ składający się z małych liter. Jej największym życzeniem jest skonstruowanie napisu $t$, dla którego spełnione są następujące warunki:
- $t$ nie zawiera $s$ jako podciągu.
- Każdy podciąg napisu $s$, który nie pokrywa się z $s$, jest zawarty w $t$ jako podciąg.
Pomóż jej znaleźć napis $t$ o minimalnej możliwej długości. Jeśli istnieje wiele takich napisów, możesz wypisać dowolny z nich.
Wejście
Jedyny wiersz wejścia zawiera napis $s$ ($2 \le |s| \le 10^6$) — napis Nadeko. Gwarantowane jest, że $s$ składa się wyłącznie z małych liter.
Wyjście
W jedynym wierszu wypisz dowolny napis $t$ o minimalnej długości spełniający warunki zadania.
Przykład
Wejście 1
aaaa
Wyjście 1
aaa
Wejście 2
bba
Wyjście 2
bab
Uwagi
W drugim przykładzie napis bab zawiera bb, ba, a, b jako podciągi, ale nie zawiera bba. Jest również oczywiste, że nie da się skonstruować poprawnego ciągu o długości $2$, więc bab jest możliwą odpowiedzią.