Code Submission Evaluation System | Login |

**Task** | Statistics

Time limit: | 1.00 s | Memory limit: | 512 MB |

Consider the following string transformation:

- append the character # to the string (we assume that # is lexicographically smaller than all 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`

becomes `babc#`

. Then, the sorted list of rotations is `#babc`

, `abc#b`

, `babc#`

, `bc#ba`

, and `c#bab`

. This yields a string `cb#ab`

.The only input line contains the transformed string of length $n+1$. Each character of the original string is between a–z.

Print the original string of length $n$.

- $1 \le n \le 10^6$

Input:

`cb#ab`

Output:

`babc`