A rotation of a string is formed by moving characters from the beginning of the string to the end of the string (or from the end to the beginning) one at a time.

For example, the rotations of word home are home, omeh, meho and ehom.

Find the lexicographically first rotation of the given string.

Input

The first and only line of the input contains a string with n characters from range a-z.

Output

Output a single line with the lexicographically first rotation of the string.

Limits

• 1 \le n \le 10^6

Example

Input:

home

Output:

ehom