Problem description


Tabelka
(tabelka)
Limit pamięci: 64 MB
Limit czasu: 0.50 s

Jasio napisał sobie na kartce jakieś słowo składające się jedynie z liter a i b. Słowo tak mu się spodobało, że wypisał sobie tabelkę wszystkich jego przesunięcia cyklicznych, jedno pod drugim (dla przypomnienia: przesunięcie cykliczne słowa a1a2an o k pozycji to słowo ak + 1ak + 2ana1a2ak). Następnie uporządkował sobie słowa uzyskanej tabelki leksykograficznie i stworzył nowe, lepsze słowo: czytając z góry na dół ostatnią kolumnę liter napisanych słów (czyli ostatnie litery uporządkowanego ciągu przesunięć cyklicznych początkowego słowa).

Jasio przygotował dla Ciebie zagadkę: poda Ci lepsze słowo, a Twoim zadaniem jest uzyskać pierwszy wiersz posortowanej tabelki Jasia. Powodzenia.

Napisz program, który: wczyta lepsze słowo Jasia uzyskane zgodnie z procedurą opisaną powyżej, wyznaczy najmniejsze leksykograficznie przesunięcie cykliczne słowa jakiegoś i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter a i b – lepsze słowo Jasia (uzyskane zgodnie z procedurą opisaną powyżej).

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno się znaleźć słowo będące w pierwszym wierszu tabeli posortowanych przesunięć cyklicznych jakiegoś słowa.

Ograniczenia

Długość słowa z wejścia nie przekracza miliona znaków.

Przykład

Wejście Wyjście
baaba
aaabb