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

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

Example

Input:
acab

Output:
abac