largest-lexicographical-rotation-ii

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^6. ( |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.

SAMPLE INPUT
bidhan

SAMPLE OUTPUT
nbidha

Source: hackerearth | Difficulty: MEDIUM
Tags: String algorithms


Solutions: