Problem description

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 a₁a₂…a_n o k pozycji to słowo a_k + 1a_k + 2…a_na₁a₂…a_k). 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

baaba

aaabb