Cho xâu \(S\). Hãy xây dựng mảng hậu tố (Suffix Array) của \(S\). Mảng hậu tố là mảng chứa các chỉ số vị trí bắt đầu của các hậu tố, được sắp xếp theo thứ tự từ điển tăng dần.

Hậu tố thứ \(i\) của xâu là xâu con từ vị trí \(i\) đến hết xâu, ký hiệu là \(S[i \ldots |S|-1]\).

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

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

Định dạng đầu ra

• In ra \(|S|\) số nguyên là mảng hậu tố, mỗi số cách nhau một khoảng trắng.

Ví dụ

Input:

banana

Output:

5 3 1 0 4 2

Ràng buộc

• 50% số điểm: \(|S| \le 1000\).
• 50% số điểm còn lại: \(|S| \le 10^5\).