Một xâu xoay được tạo ra bởi chuyển một chữ cái từ cuối lên đầu xâu. Ví dụ, các xâu xoay của abc là abc, cab, bca

Hãy xác định xâu xoay có thứ tự từ điển nhỏ nhất của xâu \(S\) cho trước.

Dữ liệu vào

• Xâu \(S\) \((|S| \le 10^6)\)

Dữ liệu ra

• In ra xâu xoay có thứ tự từ điển nhỏ nhất.

Input 1

haohuy

Output 1

aohuyh