Bidhan studies at the University of Dhaka. Recently he noticed that, some of the university students are speaking a strange language. The words used in that language are not meaningful to him. After some investigation he learned that, the students use the largest lexicographical rotation of words instead of the original words.

Word p' is a rotation of word p if,
p = a + b and
p' = b + a , where a and b are some strings ( possibly empty ) and + sign denotes the concatenation operation. w, the largest lexicographical rotation of p is the lexicographically biggest one among all possible p's.

Given a string, output it's largest lexicographical rotation.

Input

The only line of the input contains next p.

Output

Output a single line containing the largest lexicographical rotation of p.

Constraints

1 ≤ |p| ≤ 4 × 10⁶. ( |p| denotes the size of p. )
p will contain lowercase English letters only.

Example

Input:
bidhan


Output:
nbidha

Explanation

The rotations of string bidhan are

bidhan,
idhanb,
dhanbi,
hanbid,
anbidh and
nbidha.

nbidha is lexicographically biggest among all of them.