- Time limit: 1.00 s
- Memory limit: 512 MB
- append the character # to the string (we assume that # is lexicographically smaller than all other characters of the string)
- generate all rotations of the string
- sort the rotations in increasing order
- based on this order, construct a new string that contains the last character of each rotation
babc#. Then, the sorted list of rotations is
c#bab. This yields a string
The only input line contains the transformed string of length $n+1$. Each character of the original string is one of a–z.
Print the original string of length $n$.
- $1 \le n \le 10^6$