String rotation - MarisaOJ: Marisa Online Judge

String rotation

Time limit: 1000 ms
Memory limit: 256 MB
A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of `marisa` are `marisa`, `amaris`, `samari`, `isamar`, `risama` and `arisam`. Your task is to determine the lexicographically minimal rotation of a string. ### Input - The first line contains a string $S$. ### Output - Print the lexicographically minimal rotation. ### Constraints - $1 \le |S| \le 10^6$. ### Example Input: ``` marisa ``` Output: ``` amaris ```