Tý có xâu \(S\). Tìm xâu xoay vòng (rotation) có thứ tự từ điển nhỏ nhất.

Xâu xoay vòng của \(S\) là xâu \(S[i..n-1] + S[0..i-1]\) với \(0 \le i < n\).

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)), gồm các chữ cái thường a-z.

Định dạng đầu ra

• In ra xâu xoay vòng nhỏ nhất theo thứ tự từ điển.

Ví dụ

Input:

bacab

Output:

abbac

Giải thích: Các xoay vòng: bacab, acabb, cabba, abbac, bbaca. Xâu abbac là nhỏ nhất.

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).