Hãy xem xét phép biến đổi xâu sau:

1. Nối ký tự # vào xâu (giả định rằng # có thứ tự từ điển nhỏ hơn so với tất cả các ký tự khác trong xâu).
2. Tạo tất cả các vòng quay của xâu.
3. Sắp xếp các vòng quay theo thứ tự từ điển tăng dần.
4. Dựa vào thứ tự này, hãy tạo một xâu mới có chứa ký tự cuối cùng của mỗi vòng quay.

Ví dụ, xâu babc trở thành babc#. Sau đó, danh sách các phép quay được sắp xếp là #babc, abc#b, babc#, bc#ba và c#bab. Cuối cùng tạo được xâu cb#ab.

Input

• Dòng đầu vào duy nhất chứa xâu đã biến đổi có độ dài \(n + 1\). Mỗi ký tự của xâu gốc là một trong những a - z.

Output

• In ra xâu gốc có độ dài \(n\).

Constraints

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

Example

cb#ab

babc