Xâu nhỏ nhất

Petya nhận được một xâu $s$ chỉ gồm các chữ cái Latin in thường. Cậu khởi tạo thêm hai xâu rỗng $t$ và $u$, rồi chơi một trò chơi với hai loại nước đi:

• Lấy ký tự đầu của $s$ (xoá khỏi $s$) và nối vào cuối $t$.
• Lấy ký tự cuối của $t$ (xoá khỏi $t$) và nối vào cuối $u$.

Trò chơi kết thúc khi cả $s$ và $t$ đều rỗng. Nhiệm vụ của bạn là chọn dãy nước đi sao cho xâu $u$ thu được có thứ tự từ điển nhỏ nhất có thể.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các chữ cái Latin in thường, $1\le |s|\le {10}^5$.

Dữ liệu ra

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

Ràng buộc

• $1\le |s|\le {10}^5$
• $s$ chỉ gồm các chữ cái Latin in thường.

Ví dụ