Code Submission Evaluation System Login

CSES Problem Set

Minimal Rotation


Task | Statistics


CSES - Minimal Rotation

Time limit:1.00 s Memory limit:512 MB

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

Input

The only input line contains a string of length $n$. Each character is one of a–z.

Output

Print the lexicographically minimal rotation.

Constraints
Example

Input:
acab

Output:
abac