Horatio Riddle

In his youth Horatio was fond of creation the full heraldic names. And this is a hard problem - if you make a mistake, then some Duke immediately will send you directly to Yorik. The rules are simple: Duke gives Horatio his ancestral title and Horatio finds its lexicographic minimum cyclic shift. Not everyone in the Danish kingdom can do it!

But now Horatio doesn't like such sessions and he needs a successor. Try yourself in this business!

Input

One string - the Duke's ancestral title, consisting of no more than 100000 Latin lowercase letters.

Output

Print in one line the correct Duke's heraldic name.

Examples