Một phép xoay của một xâu có thể được tạo ra bằng cách di chuyển lần lượt các ký tự từ đầu đến cuối. Ví dụ, các phép xoay của acab là acab, caba, abac, và baca.

Nhiệm vụ của bạn là xác định phép xoay có thứ tự từ điển nhỏ nhất của một xâu.

Dữ liệu vào

Dòng duy nhất chứa một xâu có độ dài ~n~. Mỗi ký tự là một trong các chữ a–z.

Kết quả

In ra phép xoay có thứ tự từ điển nhỏ nhất.

Giới hạn

• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

acab

Kết quả:

abac