Biến Đổi Xâu

Cho kết quả của một phép biến đổi xâu. Phép biến đổi hoạt động: nối '#' vào cuối xâu, tạo tất cả phép xoay, sắp xếp theo thứ tự từ điển, lấy ký tự cuối cùng của mỗi xoay. Hãy khôi phục xâu gốc.

Dữ liệu vào

Một dòng chứa xâu biến đổi có độ dài $n+1$ (gồm ký tự a-z và #).

Dữ liệu ra

In ra xâu gốc có độ dài $n$.

Ràng buộc

• $1\le n\le {10}^6$

Ví dụ