Циклічний зсув рядка можна згенерувати переміщенням символів один за одним від початку до кінця.

Наприклад, циклічний зсув acab є acab, caba, abac і baca.

Ваше завдання — визначити лексикографічно мінімальний циклічний зсув рядка.

Обмеження

• \(1≤n≤10^6\)

Формат вхідних даних

Єдиний вхідний рядок містить рядок довжиною \(n\). Кожен символ є одним із символів 'a'–'z'.

Формат вихідних даних

Вивести лексикографічно мінімальний циклічний зсув.

Приклад вхідних даних

acab

Приклад вихідних даних

abac