Code Submission Evaluation System Login

CSES Problem Set

String Transform


Task | Statistics


CSES - String Transform

Time limit:1.00 s Memory limit:512 MB

Consider the following string transformation:
  1. append the character # to the string (we assume that # is lexicographically smaller than all characters of the string)
  2. generate all rotations of the string
  3. sort the rotations in increasing order
  4. based on this order, construct a new string that contains the last character of each rotation
For example, the string 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.

Input

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

Output

Print the original string of length $n$.

Constraints
Example

Input:
cb#ab

Output:
babc