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

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

Input

• Dòng đầu vào duy nhất chứa một xâu độ dài \(n\). Mỗi kí tự là một trong những a - z.

Output

• In vòng quay có thứ tự từ điển nhỏ nhất.

Constraints

• \(1 \leq n \leq 10^6\)

Example